Skip to main content

Dynamic programming builds solutions from solutions to simpler subproblems. It's closely allied to recursion, but dynamic programming algorithms are formulated as iteration usually over a very regular datastructure.

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.