Dynamic programming recursive or iterative

Question

I read about dynamic programming and am pretty new to this. I would like to know if dynamic programming can be used in an "iterative" and "recursive" way, or is it good practice to apply it to only one of the ways. Any good examples / links would be helpful.

Answer 1

Yes, DP can be applied to both.

Start here: http://en.wikipedia.org/wiki/Dynamic_programming

Then you Dynamic Programming: From Beginner to Advanced and Dynamic Programming Tutorial

In the first lesson, you will find links to TopCoder.com problems for practice (each of these problems also has an editorial that explains the idea behind the solution.

Answer 2

Dynamic programming can be seen (in many cases) as a recursive solution, implemented in the reverse order.

Usually in recursion, you compute x(n+1) = f(x(n)) with some stop condition for n=0 (or another value).

In many cases, the function f is some min / max function, but it is not required. In addition, the function should not accept one variable.

Dynamic programming would solve this problem by calculating f(0) , then f(1) , then f(2) , etc.

With more than one variable, there will usually be some natural order of function calculation.

An example that dynamic programming can solve: You are given 3 golf clubs. Each golf club can send a golf ball x units of distance ahead (e.g. 24, 37 and 54 units). The question is, can you hit a hole that is exactly 200 units? And if you can, then what is the minimum number of shots you need.

A recursive solution would look something like this:

 shots(200) = min(shots(200-24),shots(200-37),shots(200-54)) 

This would allow us to implement a trivial implementation in which the function shot(n) returns 0 if n is 0, some huge number if n is less than 0, and the expression above otherwise.

However, for large values ​​of n, you will again and again use the same values ​​from different branches of the expression above. In this case, it is best to start at 0 and calculate shots(0) , shots(1) , shots(2) , etc. It will be a "dynamic programming" solution for this problem - using linear time and constant space instead of exponential time (crossing a 3-lane tree) and linear space at best (for the call stack).