4.4Dynamic programming basics
The idea
Dynamic programming solves overlapping subproblems once and stores the answers, turning exponential recursion into a polynomial table fill.
Think of it like this: Writing down results in a notebook instead of recomputing them every time.
Why it exists
It is the main technique behind LCS, knapsack and matrix chain, and DP questions are 2-mark staples.
How it works
- Define the subproblem (the table cell) and its meaning.
- Write the recurrence from smaller cells.
- Fill the table in a valid order (or memoise).
- Time = (number of cells) × (work per cell).
Worked example: Fibonacci
The recursion makes about 1.618ⁿ calls, but only n + 1 distinct values exist: a table needs n − 1 additions.
Now play with it
- →Try n = 25 in the calculator and compare the two counts.
- →Note that memoisation gives the same bound as the table.
The recursion recomputes the same subproblems again and again (overlapping subproblems). Memoisation or a table solves each once.
Check yourself
Plain recursive Fibonacci takes time
Exam notes (the dense version)
Use DP when subproblems overlap and the problem has optimal substructure. Memoisation is top-down recursion with a cache; tabulation fills a table bottom-up. Plain recursive Fibonacci is exponential (about 1.618ⁿ calls), DP makes it O(n). Time = (number of states) × (work per state).
Previous year questions: Algorithm Design: Divide & Conquer, Greedy, DP (7)
PYQs are grouped by topic, so this is the full set for Algorithm Design: Divide & Conquer, Greedy, DP; try the ones that match this subtopic. Open all 7 on the topic page.