Dynamic Programming recursive or iterative

Question

Can Dynamic Programming be applied in an "iterative" and a "recursive" way or is it good practice to apply it only one of the ways?

Answer 1

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

Normally, in a recursion, you would calculate x(n+1) = f(x(n)) with some stop condition for n=0 (or some other value).

In many cases the function f is some min/max function, but it doesn't have to be. Also, the function doesn't have to take a single variable.

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

With more than one variable, there would normally be some natural order to calculate the function.

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 forward (for example, 24, 37 and 54 units). The question is: can you hit a hole that is exactly 200 units away? And if you can, what's the minimum number of shots you need.

The recursive solution would be something like:

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

This would allow a trivial implementation, where 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 hit the same values again and again, from different branches of the expression above. In that case, it's better just to start from 0 and calculate shots(0), shots(1), shots(2) etc. This would be the "dynamic programming" solution to this problem - using linear time and constant space instead of exponential time (traversing a 3-way tree) and linear space at best (for the call stack).