- Like divide and conquer, DP solves problems by combining solutions to subproblems.
- Unlike divide and conquer, subproblems are not independent.
However, solution to one subproblem may not affect the solutions to other subproblems of the same problem. (More on this later.)
- DP reduces computation by:
Storing solution to a subproblem the first time it is solved.
Looking up the solution when subproblem is encountered again.
- Key: determine structure of optimal solutions