The link between dynamic programming and recursion is actually very strong.

Any dynamic programming solution can be transformed into a recursive solution (with memoization), with identical performance characteristics, e.g O(n*n). The difference is primarily one of presentation.

The longest common subsequence problem is a good example of a problem that can be solved with dynamic programming.

history | show excerpt | excerpt history