User:RDSEED, CC BY-SA 4.0 · CC-BY-SA-4.0 · Wikimedia Commons
Dynamic programming is recursion plus a cache. The trigger is overlap: when the naive recursion would recompute the same subproblem $f(k)$ many times across different branches, you store each answer the first time and reuse it forever after. That’s it — find the recurrence, confirm subproblems repeat, fill a table bottom-up. The same two-step move handles climbing-stairs, grid paths, coin change, edit distance, knapsack, and most of the DP-tagged FAANG interview canon.
✓ Intro · expand
Try first (productive failure)
Before the worked example: spend 60 seconds taking your best shot at this.
A guess is fine — being briefly wrong about a problem makes the explanation
land harder when you read it. This appears once per tutorial; skip
if you already know the trick.
60s
✓ Try first · expand
Worked example
Find the length of the longest common subsequence (LCS) of the strings $A = \texttt{ABCBDAB}$ and $B = \texttt{BDCAB}$. (A subsequence keeps the original order but may drop characters; the two strings need not match contiguously.)
✓ Worked example · expand
Practice 1 of 3Type a fraction, decimal, or expression — mathjs parses it.
✓ Practice · expand
Reflection
When you looked at a problem and decided “this wants DP, not just recursion,” what was the cue? In your own words, what does “overlapping subproblems” feel like when you spot it in the call tree?
