Day 14 — Dynamic Programming
Recursion taught you to break a problem into smaller versions of itself. Dynamic Programming is what you do when those smaller versions keep showing up over and over again — instead of recomputing them, you remember the answer.
That’s the whole idea. Everything else in this chapter — memoization, tabulation, knapsack, LCS, LIS, bitmask DP — is just disciplined application of that one trick.
DP has a reputation for being the scariest topic in interviews. It isn’t. It’s the topic where pattern recognition pays off the most — once you’ve seen 15 problems, the 16th feels like rerunning a recipe. This chapter is the recipe book.
What you’ll learn today
- The two ingredients of DP: overlapping subproblems + optimal substructure
- Top-down (memoization) vs bottom-up (tabulation) — pick the right style for each problem
- The state-design checklist: identify the dimensions, the transitions, and the base cases
- The classic patterns every interviewer reaches for: Fibonacci-style 1D, grid 2D, knapsack, LIS, LCS, edit distance, coin change
- Space optimization — when you can collapse an N×N table down to one row or two
- Advanced shapes: bitmask DP, interval DP, DP on trees, DP on subsequences vs substrings
- Ten interview problems that drill every pattern into muscle memory
The secret nobody tells you about DP: 80% of the work is figuring out the state. Once you write down dp[i][j] = ...the answer for the subproblem indexed by i and j..., the transition usually falls out in one or two lines. We will obsess over state design on every problem.
Roadmap
- Introduction — what makes a problem a DP problem, the Fibonacci tax, and the two-property test (overlapping subproblems + optimal substructure).
- Memoization vs Tabulation — top-down and bottom-up, side by side. When recursion is clearer, when iteration is faster, and how to convert one to the other.
- Classic Patterns — the seven shapes that cover the majority of DP interview problems: 1D linear, 2D grid, 0/1 knapsack, unbounded knapsack, LIS, LCS, edit distance.
- Advanced DP — space optimization, bitmask DP, interval DP, DP on trees, and the “subsequence vs substring” distinction that trips everyone up.
- Basic Questions — warm-ups: climbing stairs, min cost stairs, Fibonacci with memo, house robber.
- Practice Questions — ten interview classics, one per pattern, with full state-design walkthroughs.
Recursion is the bridge into this chapter — if recursion(n) and recursion(n) show up twice in your call tree, you’ve already invented DP. The Memoization page in Day 5 is the prequel; this chapter is the full series.
Coming up next: Day 15 — Greedy Algorithms, where you’ll learn the opposite mindset — when not to remember anything, and just commit to the locally-best move.