advanced
Dynamic programming
Overlapping subproblems, optimal substructure, memoization, tabulation, and state design.
Dynamic programming applies when subproblems overlap and optimal answers can be built from smaller optimal answers. The hard part is not the table; it is choosing state that captures everything needed and nothing irrelevant. Memoization starts from recursion, while tabulation fills states in dependency order.
On interviews: Interviewers expect the recurrence, base cases, state dimensions, transition cost, and final complexity.
Common pitfalls: Do not force DP when greedy or sliding window is enough. State explosions happen when you include raw history instead of compressed facts. Watch for modulo and reconstruction requirements.
Checklist:
- Define dp state.
- Write recurrence.
- Set base cases.
- Compute dimensions times transition cost.