Discussion On Dynamic Programming

[rajibbd 0]

Dynamic Programming[DP] is one of the powerful programming approach now a day. DP applicable when sub problems share sub sub problems. (No independent sub problems). Solve each sub problem once, save the answer, and when needed use the previously computed result. Like for Fibonacci series. To get f(n+1) we need addition of f(n), f(n-1) and for f(n) we need f(n-1), f(n-2). so to get f(n+1) we need f(n) and f(n-1) and again for f(n) we need f(n-1) and f(n-2). In this approach we are calculating same thing more then once[as we need sub problem and for sub problem we need sub sub problem]. That is a very bad idea. But what if we store the data of f(n), f(n-1), f(n-1),..f(2), f(1), f(0) and reuse it while needed. That is one of the DP approach. DP is typically applied to optimization problem. Many solutions but DP find the one with minimum/maximum value. DP finds an optimal solution, rather the optimal solution.

Four steps of DP

Characterize the structure of the optimal solution.

Recursively define the value of the optimal solution.

Compute the value of the optimal solution in a bottom-up fashion.

Construct the optimal solution from computer result.

[osknockout 0]

DP finds an optimal solution, rather the optimal solution.

Alright. What on earth are you trying to say?

Anyway, isn't it common programming practice to do what you're suggesting anyway? I mean really, who actually spends time

looping through a function recursively until he gets an answer instead of simply writing some code to go from (n-1) to n?

 

Oh, and there's a name for your little technique. It's called lookup tables. Look it up.

Edited August 3, 2007 by osknockout (see edit history)

[rajibbd 0]

[cont] A problem may have many solution but we are trying to find out an optimal solution. I believe to learn a better programing language need to learn bettere technique. Dynamic Programing is use for optimize the solution. Each problem have many solution with various valus but we are trying to find out the optimal solution by using this DP approach. There are many problem who is solved under this approach. But obviously not every problem. Now you may woundering where we should apply those two method. If the problem is "Optimal Substure" and overlapping subproblems. Only then this dynamic programming can be applicable. If you need to know much about it then you better read book.

[laexter 0]

Oh, and there's a name for your little technique. It's called lookup tables. Look it up.

Actually lookup tables officially has the name "memoisation", which is one form of dynamic programming (the top-down approach). The bottom up approach is sometimes faster and sometimes slower (in bottom-up approach, you generate all the answers to all subproblems then use that for answering the real thing). Dynamic programming will be very useful in very specific problems, namely when they have overlapping subproblems (like said).

IMHO if you are interested in algorithms then proficiency in dynamic programming (and whether you know about it) is one of the "benchmark" of your programming skill.