Notes › DSA
Dynamic Programming
DP = recursion + remembering answers. If a recursive solution solves the same sub-problem again and again, store each answer once and reuse it.
A problem needs DP when it has:
- Optimal substructure — the best answer is built from best answers of smaller sub-problems.
- Overlapping sub-problems — the same sub-problems repeat.
Signal words: number of ways, minimum/maximum cost, longest/shortest, can we reach, choose or skip.
The 5-step recipe
- State — what parameters describe a sub-problem? (
dp[i]= answer for the first i items) - Transition — how does
dp[i]come from smaller states? - Base cases — the smallest states you know directly.
- Order — compute states before they are needed (or let recursion do it).
- Answer — which state is the final answer?
Memoisation vs tabulation — Fibonacci
// plain recursion: O(2ⁿ)
// 1) memoisation (top-down): O(n)
vector<long long> memo(91, -1);
long long fib(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
// 2) tabulation (bottom-up): O(n)
long long fibTab(int n) {
if (n <= 1) return n;
vector<long long> dp(n + 1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
// 3) space optimised: O(1) memory
long long fibO1(int n) {
long long a = 0, b = 1;
while (n--) { long long c = a + b; a = b; b = c; }
return a;
}
| Memoisation | Tabulation | |
|---|---|---|
| Style | recursive, top-down | loops, bottom-up |
| Easy to write from brute force | ✅ | needs the right loop order |
| Stack overflow risk | yes (deep recursion) | no |
| Space optimisation | hard | easy (keep only needed rows) |
Interview tip: write the recursion first, add memoisation, then convert to tabulation if asked.
Family 1: 1D DP
Climbing stairs (1 or 2 steps): dp[i] = dp[i-1] + dp[i-2].
House robber (no two adjacent): dp[i] = max(dp[i-1], dp[i-2] + a[i]).
Coin change (min coins):
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x && dp[x - c] != INT_MAX) dp[x] = min(dp[x], dp[x - c] + 1);
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
Family 2: grid DP
Unique paths (move right/down): dp[r][c] = dp[r-1][c] + dp[r][c-1].
Minimum path sum: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
Family 3: 0/1 knapsack (take or skip)
dp[i][w] = best value using the first i items with capacity w.
int knapsack(vector<int>& wt, vector<int>& val, int W) {
vector<int> dp(W + 1, 0); // 1D: loop w downwards so each item is used once
for (int i = 0; i < wt.size(); i++)
for (int w = W; w >= wt[i]; w--)
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
Same family: subset sum, partition equal subset sum, target sum. Unbounded knapsack (items reusable): loop w upwards.
Family 4: strings (two indices)
Longest Common Subsequence:
int lcs(string a, string b) {
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = a[i-1] == b[j-1] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);
return dp[n][m];
}
Same family: edit distance, longest palindromic subsequence, shortest common supersequence, distinct subsequences.
Family 5: Longest Increasing Subsequence
dp[i] = LIS ending at i → O(n²). The binary search method (keep the smallest tail for each length) is O(n log n).
Family 6: intervals / partitions
dp[i][j] over a range: matrix chain multiplication, burst balloons, palindrome partitioning (min cuts). Loop by length of the range.
Family 7: DP on stocks
States: day + holding/not holding (+ transactions left, cooldown). Best time to buy and sell stock I–IV.
Complexity
Time ≈ number of states × work per transition. LCS: n·m states × O(1) = O(n·m).
Classic problems
Climbing stairs · House robber I/II · Coin change I/II · Unique paths · Minimum path sum · 0/1 knapsack · Partition equal subset sum · LCS · Edit distance · LIS · Word break · Decode ways · Longest palindromic substring · Matrix chain multiplication · Buy and sell stock.
Practise in the Dynamic Programming section.
Interview one-liners
- Greedy picks the locally best choice; DP tries all choices but reuses answers.
- If the recursion tree has repeated calls, memoise it.
- State the state and transition in words before writing code — interviewers grade that.
- Use
long longand a modulo (1e9+7) when counting ways.