Dynamic Programming

Make your algorithm more efficient by storing some of the intermediate results.

Works very well when your algorithm has a lot of repetitive computations.

Solving Problems

There are typically 3 ways to solve a problem using Dynamic Programming:

1. Recursion (Naive)
   If you notice there are a lot of repeated computations, implement 2.

2. Recursion and Memoization
   If the recursion creates a call stack so massive that the stack overflows, implement 3.

3. Bottom-up
   No recursion, explicitly build the memoization storage.

Memoization

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Bibliography

MIT 6.006 - Introduction to Algorithms, Fall 2011