Dynamic Programming: Optimal Substructure & Overlapping Subproblems

DP applies when an optimal solution is built from optimal solutions of overlapping subproblems; pick a state, write a recurrence, and evaluate it bottom-up (tabulation) or top-down (memoization).