Dynamic programming (DP) combines the correctness of complete search with the speed of greedy. It works when a problem breaks into overlapping subproblems: smaller versions of itself that come up again and again. Solve each subproblem once, store the answer, and reuse it. DP is used to find an optimum (the smallest or largest value) or to count solutions. Learning to spot the right subproblem is a milestone for every competitive programmer, and this chapter’s classic problems are the best training.
Dynamic programming (DP) complete search ki sahi-pan aur greedy ki speed dono deta hai. Yeh tab chalta hai jab problem overlapping subproblems mein toot jaaye — usi problem ke chhote roop jo baar-baar aate hain. Har subproblem ek baar solve karo, answer store karo, aur reuse karo. DP ya toh optimum (sabse chhota/bada) nikaalta hai, ya solutions ginta hai. Sahi subproblem pehchaanna har competitive programmer ke liye ek milestone hai — aur is chapter ke classic problems sabse achhi training hain.
7.1Coin problem
The recursive formulation
Back to the coin problem from chapter 6, now for any coin set. Let solve(x) be the fewest coins that make the sum x. The key idea is to focus on the first coin c. After it, what remains is the same problem for x − c:
Chapter 6 wala coin problem — ab kisi bhi coin set ke liye. solve(x) = sum x banane ke liye kam se kam coins. Asli idea: pehle coin c pe dhyaan do — uske baad bacha hua kaam wahi problem hai, bas x − c ke liye:
For coins {1, 3, 4}: solve(10) = solve(7) + 1 = solve(4) + 2 = solve(0) + 3 = 3, using 3 + 3 + 4. Coding this recursion directly is correct but exponential, because the same solve(x) gets recomputed many times.
Coins {1, 3, 4} ke liye: solve(10) = solve(7) + 1 = solve(4) + 2 = solve(0) + 3 = 3 (3 + 3 + 4). Is recursion ko seedha likhna sahi hai par exponential — wahi solve(x) baar-baar calculate hota hai.
/** Correct, but exponential: the same sums are recomputed over and over. */static int solveSlow(int x) { if (x < 0) return INF; if (x == 0) return 0; int best = INF; for (int c : coins) best = Math.min(best, solveSlow(x - c) + 1); return best;}Memoization, then iteration
Memoization stores each solve(x) the first time it is computed (ready[x], value[x]) and returns the stored value afterwards. Now each x is computed once, so the time is O(n·k) for n the sum and k the number of coins. Most contestants then write the same thing bottom-up: fill value[0..n] in increasing order, so every value[x − c] is already known. It’s shorter, has no recursion depth limit, and has smaller constants.
Memoization har solve(x) ko pehli baar calculate hote hi store kar leta hai (ready[x], value[x]) aur baad mein seedha woh value lauta deta hai. Ab har x ek hi baar calculate hota hai — time O(n·k) (n = sum, k = coins). Zyaadatar contestants yahi cheez bottom-up likhte hain: value[0..n] badhte order mein bharo, taaki har value[x − c] pehle se pata ho. Chhota code, recursion depth ka jhanjhat nahi, chhote constants.
static boolean[] ready;static int[] value; /** Same recursion, but each solve(x) is computed once and remembered: O(n·k). */static int solve(int x) { if (x < 0) return INF; if (x == 0) return 0; if (ready[x]) return value[x]; int best = INF; for (int c : coins) best = Math.min(best, solve(x - c) + 1); value[x] = best; ready[x] = true; return best;}/** Bottom-up: fill value[0..n] in increasing order. Also records the first coin of an optimal solution. */static int[] first; static int minCoins(int n) { int[] best = new int[n + 1]; first = new int[n + 1]; best[0] = 0; for (int x = 1; x <= n; x++) { best[x] = INF; for (int c : coins) { if (x - c >= 0 && best[x - c] + 1 < best[x]) { best[x] = best[x - c] + 1; first[x] = c; } } } return best[n];}- being read
- current
- just written
- path to root
value[x] = fewest coins for sum x. value[0] = 0. Fill x = 1..10 in order, so smaller sums are always ready.
/** Bottom-up: fill value[0..n] in increasing order. Also records the first coin of an optimal solution. */static int[] first; static int minCoins(int n) { int[] best = new int[n + 1]; first = new int[n + 1]; best[0] = 0; for (int x = 1; x <= n; x++) { best[x] = INF; for (int c : coins) { if (x - c >= 0 && best[x - c] + 1 < best[x]) { best[x] = best[x - c] + 1; first[x] = c; } } } return best[n];}Constructing a solution, and counting
- Reconstruct: also remember
first[x], the coin that achieved the optimum. Then walk n → n − first[n] → … to list the coins. - Count: to count the ways (ordered), replace
minwith a sum: count[x] = Σ count[x − c], with count[0] = 1. For{1, 3, 4}there are 6 ways to make 5. The counts explode, so problems ask for them modulo 10⁹ + 7.
- Solution banana: saath mein
first[x]yaad rakho — woh coin jisne optimum diya. Phir n → n − first[n] → … chalke coins likh do. - Ginna: tareeke ginne ho (ordered) toh
minki jagah sum: count[x] = Σ count[x − c], count[0] = 1.{1, 3, 4}se 5 banane ke 6 tareeke. Counts bahut bade ho jaate hain, isliye problems modulo 10⁹ + 7 maangti hain.
static List<Integer> construct(int n) { List<Integer> used = new ArrayList<>(); while (n > 0) { used.add(first[n]); n -= first[n]; } return used;}static final int MOD = 1_000_000_007; /** Ordered ways to form each sum: count[x] = Σ count[x − c]. */static long ways(int n) { long[] count = new long[n + 1]; count[0] = 1; for (int x = 1; x <= n; x++) { for (int c : coins) { if (x - c >= 0) { count[x] = (count[x] + count[x - c]) % MOD; } } } return count[n];}My notesMere notes
7.2Longest increasing subsequence
Problem: the longest subsequence (not necessarily contiguous) whose values strictly increase from left to right. In [6, 2, 5, 1, 7, 4, 8, 3] it has length 4, for example 2, 5, 7, 8.
Subproblem: length(k) = the longest increasing subsequence that ends at position k. It is 1 plus the best length(i) over earlier positions i with a[i] < a[k], or just 1 if there is none. The answer is the maximum over all k, in O(n²).
Problem: sabse lamba subsequence (lagaatar hona zaroori nahi) jiski values left se right strictly badhti hon. [6, 2, 5, 1, 7, 4, 8, 3] mein length 4 — jaise 2, 5, 7, 8.
Subproblem: length(k) = position k pe khatam hone wala sabse lamba increasing subsequence. Yeh 1 + un pichhli positions i ka best length(i) hai jahan a[i] < a[k] — aur aisa koi na ho toh bas 1. Answer = saare k ka maximum, O(n²) mein.
/** length[k] = longest increasing subsequence that ends exactly at position k. */static int[] lengths(int[] a) { int n = a.length; int[] length = new int[n]; for (int k = 0; k < n; k++) { length[k] = 1; for (int i = 0; i < k; i++) { if (a[i] < a[k]) { length[k] = Math.max(length[k], length[i] + 1); } } } return length;}- current
- being read
- ruled out
- just written
- one longest subsequence
length[k] = longest increasing subsequence ending exactly at k. For each k, look at every earlier i with a[i] < a[k].
/** length[k] = longest increasing subsequence that ends exactly at position k. */static int[] lengths(int[] a) { int n = a.length; int[] length = new int[n]; for (int k = 0; k < n; k++) { length[k] = 1; for (int i = 0; i < k; i++) { if (a[i] < a[k]) { length[k] = Math.max(length[k], length[i] + 1); } } } return length;}/** tails[L] = the smallest possible last element of an increasing subsequence of length L + 1. */static int lisFast(int[] a) { int[] tails = new int[a.length]; int len = 0; for (int x : a) { int lo = 0, hi = len; // first tail ≥ x (lower bound) while (lo < hi) { int mid = (lo + hi) >>> 1; if (tails[mid] >= x) hi = mid; else lo = mid + 1; } tails[lo] = x; // x either extends the longest run or improves a tail if (lo == len) len++; } return len;}My notesMere notes
7.3Paths in a grid
Problem: go from the upper-left to the lower-right corner of an n × n grid, moving only down or right, and maximise the sum of the squares you visit. A path into square (y, x) comes either from the left or from above, so
sum(y, x) = max(sum(y, x − 1), sum(y − 1, x)) + value(y, x),
with an extra row and column of zeros at index 0 so the edges need no special case. The book’s grid gives 67, in O(n²).
Problem: n × n grid ke upper-left se lower-right corner tak jao, sirf neeche ya right chalke, aur raaste ke squares ka sum maximum karo. Square (y, x) tak path ya left se aata hai ya upar se, toh
sum(y, x) = max(sum(y, x − 1), sum(y − 1, x)) + value(y, x),
index 0 pe zeros ki ek extra row/column ke saath taaki edges pe koi special case na ho. Book ka grid 67 deta hai, O(n²) mein.
/** value is 1-indexed: value[1..n][1..n]; row 0 and column 0 are 0 so the edges need no special case. */static long[][] sums(int[][] value, int n) { long[][] sum = new long[n + 1][n + 1]; for (int y = 1; y <= n; y++) { for (int x = 1; x <= n; x++) { sum[y][x] = Math.max(sum[y][x - 1], sum[y - 1][x]) + value[y][x]; } } return sum;}- current
- being read
- just written
- best path
sum(y, x) = the best path sum ending at (y, x). A path can only arrive from the left or from above.
/** value is 1-indexed: value[1..n][1..n]; row 0 and column 0 are 0 so the edges need no special case. */static long[][] sums(int[][] value, int n) { long[][] sum = new long[n + 1][n + 1]; for (int y = 1; y <= n; y++) { for (int x = 1; x <= n; x++) { sum[y][x] = Math.max(sum[y][x - 1], sum[y - 1][x]) + value[y][x]; } } return sum;}My notesMere notes
7.4Knapsack problems
Knapsack problems pick a subset of objects with some property. Problem: given weights, which sums can a subset make? For [1, 3, 3, 5], every sum from 0 to 12 is possible except 2 and 10.
Subproblem: possible(x, k) asks whether the first k weights can make x. Either weight k is used, which leaves x − w_k for the first k − 1 weights, or it isn’t, which leaves x for the first k − 1. That’s O(nW) for W the total weight.
A one-dimensional array is enough. For each weight, update the sums from right to left, so a sum created in this round isn’t extended again by the same weight.
Knapsack problems objects ka koi subset chunte hain jisme koi property ho. Problem: weights diye hain — subset se kaunse sums ban sakte hain? [1, 3, 3, 5] se 0 se 12 tak har sum, sirf 2 aur 10 ko chhodkar.
Subproblem: possible(x, k) — kya pehle k weights se x ban sakta hai? Ya toh weight k use hua (bacha x − w_k pehle k − 1 se), ya nahi hua (bacha x pehle k − 1 se). O(nW), jahan W = total weight.
Ek one-dimensional array kaafi hai: har weight ke liye sums right se left update karo, taaki isi round mein bana sum usi weight se dobara na badhe.
/** possible[k][x]: can the first k weights make the sum x? (w is 1-indexed) */static boolean[][] table(int[] w, int n, int W) { boolean[][] possible = new boolean[n + 1][W + 1]; possible[0][0] = true; for (int k = 1; k <= n; k++) { for (int x = 0; x <= W; x++) { if (x - w[k] >= 0 && possible[k - 1][x - w[k]]) possible[k][x] = true; if (possible[k - 1][x]) possible[k][x] = true; } } return possible;}- just written
- from: use weight k
- from: skip weight k
possible[k][x]: can the first k weights make the sum x? With no weights, only 0 is possible.
/** possible[k][x]: can the first k weights make the sum x? (w is 1-indexed) */static boolean[][] table(int[] w, int n, int W) { boolean[][] possible = new boolean[n + 1][W + 1]; possible[0][0] = true; for (int k = 1; k <= n; k++) { for (int x = 0; x <= W; x++) { if (x - w[k] >= 0 && possible[k - 1][x - w[k]]) possible[k][x] = true; if (possible[k - 1][x]) possible[k][x] = true; } } return possible;}/** One array, updated from right to left so each weight is used at most once. */static boolean[] sums(int[] w, int W) { boolean[] possible = new boolean[W + 1]; possible[0] = true; for (int wk : w) { for (int x = W - wk; x >= 0; x--) { if (possible[x]) possible[x + wk] = true; } } return possible;}/** 0/1 knapsack: the largest total value with total weight ≤ cap. */static long bestValue(int[] weight, int[] value, int cap) { long[] best = new long[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int c = cap; c >= weight[i]; c--) { best[c] = Math.max(best[c], best[c - weight[i]] + value[i]); } } return best[cap];}My notesMere notes
7.5Edit distance
The edit distance (Levenshtein distance) is the fewest inserts, removes and modifications that turn one string into another. LOVE → MOVIE takes 2: modify L→M, then insert I.
Subproblem: distance(a, b) between the prefixes x[0..a] and y[0..b]. The last step was one of three things:
- insert a character: distance(a, b − 1) + 1;
- remove a character: distance(a − 1, b) + 1;
- match or modify the last characters: distance(a − 1, b − 1) + (0 if they’re equal, else 1).
Take the minimum. The table is O(nm), and walking back from the corner reads off the actual operations.
Edit distance (Levenshtein distance) = ek string ko doosri mein badalne ke liye kam se kam inserts, removes aur modifications. LOVE → MOVIE mein 2 lagte hain: L→M modify, phir I insert.
Subproblem: prefixes x[0..a] aur y[0..b] ke beech distance(a, b). Aakhri step teen mein se ek tha:
- character insert: distance(a, b − 1) + 1;
- character remove: distance(a − 1, b) + 1;
- aakhri characters match ya modify: distance(a − 1, b − 1) + (barabar hon toh 0, warna 1).
Minimum lo. Table O(nm) ki hai, aur corner se peeche chalne pe asli operations padh lo.
/** d[a][b] = edit distance between the first a characters of x and the first b of y. */static int[][] table(String x, String y) { int n = x.length(), m = y.length(); int[][] d = new int[n + 1][m + 1]; for (int a = 0; a <= n; a++) d[a][0] = a; // remove everything for (int b = 0; b <= m; b++) d[0][b] = b; // insert everything for (int a = 1; a <= n; a++) { for (int b = 1; b <= m; b++) { int cost = x.charAt(a - 1) == y.charAt(b - 1) ? 0 : 1; d[a][b] = Math.min(Math.min(d[a][b - 1] + 1, d[a - 1][b] + 1), d[a - 1][b - 1] + cost); } } return d;}- just written
- being read
- match (cost 0)
- operations path
d[a][b] = edit distance between the first a letters of LOVE and the first b of MOVIE. The first row and column are inserts and removes.
/** d[a][b] = edit distance between the first a characters of x and the first b of y. */static int[][] table(String x, String y) { int n = x.length(), m = y.length(); int[][] d = new int[n + 1][m + 1]; for (int a = 0; a <= n; a++) d[a][0] = a; // remove everything for (int b = 0; b <= m; b++) d[0][b] = b; // insert everything for (int a = 1; a <= n; a++) { for (int b = 1; b <= m; b++) { int cost = x.charAt(a - 1) == y.charAt(b - 1) ? 0 : 1; d[a][b] = Math.min(Math.min(d[a][b - 1] + 1, d[a - 1][b] + 1), d[a - 1][b - 1] + cost); } } return d;}My notesMere notes
7.6Counting tilings
Sometimes a DP state is more than a number or two. Problem: in how many ways can 1 × 2 dominoes tile an n × m grid? A 4 × 7 grid has 781 ways. Go row by row. What a row needs to know about the previous one is just which columns are already covered by a vertical domino sticking down from above, and that’s a bitmask of m bits.
So count[row][mask] counts the partial tilings where the boundary has that mask. For each mask, fill the row: covered cells are skipped, and every other cell starts either a horizontal domino or a vertical one that sticks into the next row. The result is O(n · 4^m) at worst, so rotate the grid so that m is the shorter side.
Kabhi-kabhi DP state ek-do numbers se zyada hoti hai. Problem: 1 × 2 dominoes se n × m grid kitne tareeke se dhak sakte hain? 4 × 7 grid ke 781 tareeke. Row by row chalo. Ek row ko pichhli row ke baare mein bas itna jaanna hai ki kaunse columns upar se aate vertical domino se pehle hi dhake hain — yaani m bits ka ek bitmask.
Toh count[row][mask] un partial tilings ko ginta hai jinki boundary pe yeh mask hai. Har mask ke liye row bharo: dhake cells skip, aur baaki har cell pe ya toh horizontal domino shuru hota hai ya vertical, jo agli row mein ghus jaata hai. Worst case O(n · 4^m) — isliye grid ghumao taaki m chhoti side ho.
static int n, m;static long[][] count; // count[row][mask]: ways where `mask` marks the columns of row `row` already covered from above static long tilings(int rows, int cols) { n = rows; m = cols; count = new long[n + 1][1 << m]; count[0][0] = 1; for (int row = 0; row < n; row++) { for (int mask = 0; mask < 1 << m; mask++) { if (count[row][mask] != 0) fill(row, mask, 0, 0); } } return count[n][0];} /** Cover row `row` from column `col`; `next` collects vertical tiles sticking down into the next row. */static void fill(int row, int mask, int col, int next) { if (col == m) { count[row + 1][next] += count[row][mask]; return; } if ((mask >> col & 1) == 1) { // covered by a tile from above fill(row, mask, col + 1, next); return; } fill(row, mask, col + 1, next | 1 << col); // vertical tile down if (col + 1 < m && (mask >> (col + 1) & 1) == 0) fill(row, mask, col + 2, next); // horizontal tile}- current
- just written
- answer
Column r is the boundary above row r. A mask marks (▾) the columns already covered by a vertical tile sticking down from the row above.
static int n, m;static long[][] count; // count[row][mask]: ways where `mask` marks the columns of row `row` already covered from above static long tilings(int rows, int cols) { n = rows; m = cols; count = new long[n + 1][1 << m]; count[0][0] = 1; for (int row = 0; row < n; row++) { for (int mask = 0; mask < 1 << m; mask++) { if (count[row][mask] != 0) fill(row, mask, 0, 0); } } return count[n][0];} /** Cover row `row` from column `col`; `next` collects vertical tiles sticking down into the next row. */static void fill(int row, int mask, int col, int next) { if (col == m) { count[row + 1][next] += count[row][mask]; return; } if ((mask >> col & 1) == 1) { // covered by a tile from above fill(row, mask, col + 1, next); return; } fill(row, mask, col + 1, next | 1 << col); // vertical tile down if (col + 1 < m && (mask >> (col + 1) & 1) == 0) fill(row, mask, col + 2, next); // horizontal tile}