DYNAMIC PROGRAMMING REQUIREMENTS

Requirements:

a) Optimal Substructure

b) Overlapping subproblem

Steps:

1) Characterize the structure of an optimal solution

2) Formulate a recursive solution

3) Compute the value of an opt. solution bottom-up. (get value rather than the structure)

4) Construct an optimal solution (structure) from computed infomation.

Memoization: Top-down, compute and store first time, reuse subsequent times.

• Observation 1: Optimal Substructure
• Observation 2: Overlapping Subproblems
• Memoize
• Dynamic Programming Implimentation