Re learning Dynamic Programming

 

Solving dynamic programming problems (Cormen et al)

1. Characterize the structure of an optimal solution

2. Recursively define the value of an optimal solution

3. Compute the value of an optimal solution, typically in a bottom up version

4. Construct an optimal solution from computed information 

exhibits optimal substructure, optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently

A dynamic-programming approach runs in polynomial time when the number of distinct subproblems involved is polynomial in the input size and we can solve each such subproblem in polynomial time

There are usually two equivalent ways to implement a dynamic-programming approach. The first approach is top-down with memoization. The second approach is the bottom-up method.