Dynamic Programming

• Identify a collection of subproblems.
• Build up solutions into solutions to larger problems.
• Solving an implicit dag of subproblems.
• Top-Down: recursion with memoization; starting with largest subproblem, query downwards.
• Bottom-up: filling out a table; start with smallest subproblems, built upwards.