Menu
In old games era, we are used to have a look-up table of pre-computed values of sin and cos,..etc, due to the slowness of computing those values in that old CPUs.
Is that considered a dynamic programming technique ? or dynamic programming must solve a recursive function that is always computed or sort of ?
Update: In dynamic programming the key is to have a memoization table, which is the solution for the sin,cos look up table, so what is really the difference in the technique ?
869
The Lookup Table Dynamic block computes an approximation of a function y = f(x) using xdat and ydat vectors. The lookup method can use interpolation, extrapolation, or the original values of the input. Using the Lookup Table Dynamic block, you can change the table data without stopping the simulation.
A lookup table is an array of data that maps input values to output values, thereby approximating a mathematical function. Given a set of input values, a lookup operation retrieves the corresponding output values from the table.
Lookup tables provide the essential function of helping you maintain data integrity in your database environment. For example, if you have users entering their gender into a data item, the table that contains the Gender item can reference a lookup table to verify that only the value M or F is used.
Well a lookup table is simply an initialized array that contains precalculated information. They are typically used to avoid performing complex (and hence time consuming) calculations. For example, it is well known that the speed of CRC calculations may be significantly increased by use of a lookup table.
I'd say for what I see in your question no it's not dynamic programming. Dynamic programming is more about solving problems by solving smaller subproblem and create way to get solution of problem from smaller subproblem.
Your situation looks more like memoization.
For me it could be considered DP if your problem was to compute cos N and you have formula to calculate cos i from array of cos 0, cos 1, ..., cos i - 1, so you calculate cos 1, sin 1 and run you calculation for i from 0 to N.
May be somebody will correct me :)
There's also interesting quote about how dynamic programming differ from divide-and-conquer paradigm:
There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping subproblems. If a problem can be solved by combining optimal solutions to non-overlapping subproblems, the strategy is called "divide and conquer" instead. This is why mergesort and quicksort are not classified as dynamic programming problems.
51
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
