3 ms·
Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?
by zestyping 8y ago
Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?
- sn41 8y agoIt is basically memoized recursion. However, that does not mean that it is easy. To find out the optimal substructure - that is, building the solution to the problem from the optimal solution of its subproblem decomposition - is where the actual difficulty of the technique lies. Exercises from a standard algorithm textbook like Kleinberg and Tardos should give enough practice in solving these problems. Not all of them are straightforward.
- gowld 8y agoConsider Fibonacci. Memoized recursion uses O(n) memory, because you don't garbage-collect anything. Bottom-up dynamic programming is O(1) memory, because you only need to remember the largest 2 subvalues you've computed.
- ufo 8y agoPretty much. Although sometimes it is more natural to build up the solution "bottom up" instead of using memoization. The tricky bit is figuring out what is the recurrence relation (recursion) for the problem you are trying to solve.