Dynamic Programming (DP) is an algorithm design technique for problems that exhibit two structural properties:
| Property | Meaning |
|---|---|
| Optimal substructure | The optimal solution to the whole problem can be built from optimal solutions to its sub-problems. |
| Overlapping sub-problems | The same smaller problems recur many times during a naive recursive computation. |
When both properties hold, storing sub-problem answers (instead of recomputing them) converts exponential naive recursion into polynomial time.
Every DP solution follows the same three-step ritual:
Identify what a single cell dp[i] (or dp[i][j]) represents.
A precise state definition is the hardest and most important step.
Example:
dp[i] = number of distinct ways to reach step i.
Express dp[i] in terms of smaller sub-problems.
Example:
dp[i] = dp[i-1] + dp[i-2](Climbing Stairs).
Identify the smallest sub-problems whose answers are known without recursion.
Example:
dp[1] = 1,dp[2] = 2(Climbing Stairs).
Problem
│
├─► Top-Down (Memoization)
│ Recursive function + cache (dict / @lru_cache)
│ Natural to write; call-stack depth is O(n)
│
└─► Bottom-Up (Tabulation)
Fill a table iteratively from base cases upward
No recursion overhead; explicit memory layout
│
└─► Rolling-Variable Optimisation
When dp[i] depends only on the last k values,
replace the O(n) array with k variables → O(1) space
When to use each:
| Strategy | When |
|---|---|
| Memoisation | Recurrence is clear, sub-problem graph is sparse or irregular |
| Tabulation | Linear / grid structure; want to avoid recursion overhead |
| Rolling variables | Table needed only last 1–2 rows; memory is constrained |
Dynamic Programming is not just a coding-interview topic — it is foundational to several ML/AI algorithms:
- Viterbi algorithm (HMMs, sequence labelling): finds the most-likely hidden state sequence via DP on a trellis — identical structure to min-cost path DP.
- Beam search / CTC decoding: approximate DP over sequence hypotheses used in ASR and NLP generation.
- Dynamic Time Warping (DTW): measures similarity between time series via a 2-D DP table; used in speech recognition and gesture detection.
- Reinforcement Learning (Bellman equations): the value-function update
V(s) = r + γ·V(s')is a DP recurrence over states. - Edit distance / sequence alignment: bioinformatics, fuzzy matching, and text diff all reduce to 2-D DP.
| # | Problem | State / Recurrence | Time | Space |
|---|---|---|---|---|
| 509 | Fibonacci Number | dp[i] = dp[i-1] + dp[i-2]; base dp[0]=0, dp[1]=1 |
O(n) | O(1) rolling |
| 70 | Climbing Stairs | dp[i] = dp[i-1] + dp[i-2]; base dp[1]=1, dp[2]=2 |
O(n) | O(1) rolling |
| 746 | Min Cost Climbing Stairs | dp[i] = cost[i] + min(dp[i-1], dp[i-2]); answer = min(dp[n-1], dp[n-2]) |
O(n) | O(1) rolling |
| 118 | Pascal's Triangle | tri[i][j] = tri[i-1][j-1] + tri[i-1][j]; edges = 1 |
O(n²) | O(n²) output |
| 119 | Pascal's Triangle II | same recurrence, single row in-place right-to-left update | O(k²) | O(k) |
| 198 | House Robber | dp[i] = max(dp[i-1], dp[i-2] + nums[i]); base dp[0]=nums[0] |
O(n) | O(1) rolling |
| 213 | House Robber II | run House Robber on nums[0:-1] and nums[1:], take max |
O(n) | O(1) rolling |
| 5 | Longest Palindromic Substring | expand-around-centre; dp[i][j] = dp[i+1][j-1] and s[i]==s[j] (implicit) |
O(n²) | O(1) |
| # | Problem | State / Recurrence | Time | Space |
|---|---|---|---|---|
| 91 | Decode Ways | dp[i] = (one-digit valid)×dp[i-1] + (two-digit valid)×dp[i-2]; base dp[0]=1 |
O(n) | O(1) rolling |
| 322 | Coin Change | dp[a] = min(dp[a-c]+1 for c in coins); base dp[0]=0 |
O(n×amount) | O(amount) |
| 152 | Maximum Product Subarray | track cur_max and cur_min; new_max = max(num, cur_max×num, cur_min×num) |
O(n) | O(1) rolling |
| 139 | Word Break | dp[i] = any(dp[j] and s[j:i] in word_set for j<i); base dp[0]=True |
O(n²×L) | O(n+W) |
| 300 | Longest Increasing Subsequence | O(n²): dp[i]=1+max(dp[j] for j<i if nums[j]<nums[i]); O(n log n): patience sort with bisect |
O(n log n) | O(n) |
| 416 | Partition Equal Subset Sum | dp[s] |= dp[s-num] right-to-left (0/1 knapsack); target = (sum+target)/2 |
O(n×target) | O(target) |
| 647 | Palindromic Substrings | expand-around-centre for 2n-1 centres; count each valid expansion | O(n²) | O(1) |
| # | Problem | State / Recurrence | Time | Space |
|---|---|---|---|---|
| 62 | Unique Paths | dp[r][c] = dp[r-1][c] + dp[r][c-1]; edges = 1 |
O(m×n) | O(n) rolling row |
| 1143 | Longest Common Subsequence | dp[i][j] = dp[i-1][j-1]+1 if match, else max(dp[i-1][j], dp[i][j-1]) |
O(m×n) | O(n) rolling row |
| 309 | Buy/Sell Stock with Cooldown | state machine: hold/sold/rest; hold=max(hold, rest-p), sold=hold+p, rest=max(rest,sold) |
O(n) | O(1) |
| 518 | Coin Change II | dp[a] += dp[a-coin]; outer=coins, inner=amounts (avoids permutations) |
O(amount×coins) | O(amount) |
| 494 | Target Sum | reduce to subset-sum count; dp[s] += dp[s-num] right-to-left; target P=(total+target)/2 |
O(n×P) | O(P) |
| 97 | Interleaving String | dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1]) |
O(m×n) | O(n) rolling |
| 72 | Edit Distance | dp[i][j] = dp[i-1][j-1] if match, else 1+min(replace, delete, insert) |
O(m×n) | O(n) rolling |
| # | Problem |
|---|---|
| 10 | Regular Expression Matching |
| 312 | Burst Balloons |
| 354 | Russian Doll Envelopes |