Recursion plus a cache — and the judgement to know when that is the right move.
Four lessons, written to the course standard. The first decides whether DP applies, the second is how to write one, and the last two work the classic problems in one and two dimensions with every answer checked against brute force.
The one idea: a slow recursion is usually slow because it solves the same subproblem thousands of times. Dynamic programming is noticing that and stopping it. Everything else — tables, loops, rolling arrays — is bookkeeping around that single observation.
Why this is a folder and not one note
Because “dynamic programming” names four separable skills, and people who struggle with DP have usually mastered the last one and skipped the first two:
- Deciding it applies — overlapping subproblems and optimal substructure, both testable rather than intuited.
- Designing the state — the part that is genuinely hard, and where almost all failed attempts go wrong.
- Writing it — memoise or tabulate, in whichever order the transition dictates.
- Doing the classics — the problems everyone recognises.
A note that starts at step 4 teaches you to recognise problems you have already seen. This folder starts at step 1.
The lessons
- What Makes a Problem DP — [Intermediate] — the two properties, both measured rather than asserted: overlap by counting distinct subproblems against total calls (Fibonacci scores 86,856×, merge sort scores 1.0×), and optimal substructure by the graph where the longest simple path has optimal sub-answers that cannot be combined. Plus why greedy fails on coin change without that being a failure of optimal substructure.
- Memoisation and Tabulation — [Intermediate] — the three declarations every DP is made of — state, transition, base case — then top-down versus bottom-up, why the transition dictates the fill order (and what a wrong order silently produces), and how to throw away a whole dimension of memory.
- Classic One-Dimensional DP — [Intermediate] — house robber, coin change and longest increasing subsequence. LIS is the one that teaches: its obvious state cannot produce a transition, and understanding why is the most transferable idea here.
- Classic Two-Dimensional DP — [Intermediate → Advanced] — LCS, 0/1 knapsack and edit distance, with reconstruction for each — and the loop direction that separates 0/1 knapsack from the unbounded one.
The thread through all four
The state is the whole design. Once you can finish the sentence “dp[i] is the …” correctly, the transition usually writes itself and the code is transcription. Most DP failures are a state that does not carry enough information to compute the next state from — which is precisely why LIS needs “ending at ” rather than “within ”.
Complexity is states × transition cost. That product is how you evaluate a candidate state before writing code. If it is too large, no implementation trick rescues it; you need a different state.
Caching removes redundancy; it does not create efficiency. Memoising an exponential-state recursion gives you an exponential DP. The cache only helps when subproblems actually repeat, which is lesson 01’s measurement.
The fill order is derived, not chosen. Every cell a transition reads must already be final. Getting this wrong produces silent zeros rather than an error — the most common way a tabulated DP is confidently wrong.
How this sits against the other techniques
| Overlapping subproblems? | Optimal substructure? | Technique |
|---|---|---|
| no | yes | divide and conquer |
| yes | yes | dynamic programming |
| yes | no | no efficient method known (longest simple path is NP-hard) |
| no | no | brute force or backtracking |
And inside row two: when a local rule provably selects the right subproblem, skip the table and use a greedy algorithm — which needs a proof, not a feeling.
What is verified
Every lab was executed and its expected output generated from that run. Every DP answer in this folder is asserted against brute force, not merely printed:
| Lesson | What the lab demonstrates |
|---|---|
| properties | merge sort’s redundancy at exactly 1.0× against Fibonacci’s 86,856×; the longest-simple-path sub-answers composing into a walk that repeats a vertex; greedy coin change failing on |
| memo/tab | a reversed fill order returning 0 instead of 34, with no error; memoised(50,000) raising RecursionError where the tabulated version is fine |
| 1-D | house robber, coin change and LIS each agreeing with brute force on 300–400 random inputs; the LIS tails array shown not to be a subsequence of the input |
| 2-D | the rolling knapsack’s upward loop returning 15 where the answer is 5 — and the first test instance hiding the bug by coincidence |
Question banks
One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.
- What Makes a Problem DP
- Memoisation & Tabulation
- Classic One-Dimensional DP
- Classic Two-Dimensional DP
Related
- 03-algorithms — the parent folder
- Recursion — where memoisation first appears, and the recurrences behind the costs
- Divide and Conquer — the technique for when subproblems do not overlap
- Greedy Algorithms — the special case where a local rule is provably enough
- The DP pattern note — the problem-recognition layer above this folder
- Floyd–Warshall — a DP over graphs
- NeetCode 150 — the DP section, for fluency
Software engineering
Infrastructure & security
Computer science
Hardware & engineering