Dynamic Programming

When to use

• Recognizing whether a problem has overlapping subproblems and optimal substructure
• Choosing between top-down memoization and bottom-up tabulation
• Designing state variables and minimizing state space dimensions
• Implementing knapsack, sequence (LCS, LIS, edit distance), interval, or grid DP patterns
• Applying bitmask DP for small subset enumeration (n ≤ 20)
• Optimizing O(n²) DP transitions with convex hull trick or D&C optimization

Core principles

1. State captures everything — if future decisions need more information, the state is incomplete
2. Bottom-up for production — no stack overflow, easier space optimization, predictable memory access
3. Rolling array before adding a dimension — space optimization is almost always possible
4. Bitmask DP is exact exponential, not a hack — O(2^n × n) is acceptable for n ≤ 20
5. Identify the DAG — every DP is a shortest/longest path on a state DAG; if you can draw it, you can implement it