Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

history | excerpt history