Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Write the brute-force recursion, notice repeated calls, and cache them. Then, optionally, turn it into a bottom-up table. Always say the state and the recurrence out loud first.
Dynamic programming applies when an answer is built from answers to smaller versions of the same question, and those smaller questions repeat. Define the state, write the recurrence, and compute each state once: top-down with a memo, or bottom-up with a table.
Typical cost: O(states × transitions)
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Coin Change
The problem statement, then the plan you would say out loud.
Fewest coins to make amount; -1 if impossible.
Plan before you code
- State: best[a] = fewest coins for amount a.
- Recurrence: best[a] = 1 + min(best[a − coin]).
- Fill amounts from 1 upwards.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Top-down with memo
1function minCostClimb(cost: number[]): number {2 const n = cost.length;3 const memo = new Map<number, number>();4 const dp = (i: number): number => { // min cost to reach the top from step i5 if (i >= n) return 0;6 if (!memo.has(i)) memo.set(i, cost[i] + Math.min(dp(i + 1), dp(i + 2)));7 return memo.get(i)!;8 };9 return Math.min(dp(0), dp(1));10}1fun minCostClimb(cost: IntArray): Int {2 val n = cost.size3 val memo = HashMap<Int, Int>()4 fun dp(i: Int): Int { // min cost to reach the top from step i5 if (i >= n) return 06 return memo.getOrPut(i) { cost[i] + minOf(dp(i + 1), dp(i + 2)) }7 }8 return minOf(dp(0), dp(1))9}1static int minCostClimb(int[] cost) {2 Map<Integer, Integer> memo = new HashMap<>();3 return Math.min(dp(0, cost, memo), dp(1, cost, memo));4}5 6// min cost to reach the top from step i7static int dp(int i, int[] cost, Map<Integer, Integer> memo) {8 if (i >= cost.length) return 0;9 Integer hit = memo.get(i);10 if (hit != null) return hit;11 int best = cost[i] + Math.min(dp(i + 1, cost, memo), dp(i + 2, cost, memo));12 memo.put(i, best);13 return best;14}- State: the cheapest way to finish from step i.
- Base case: past the end costs nothing.
- Recurrence: pay this step, then take the better next move. A Map memoises each state once.
3.2Solution
Strict TypeScript, type-checked and tested.
Coin Change
1function coinChange(coins: number[], amount: number): number {2 const best = new Array<number>(amount + 1).fill(Infinity);3 best[0] = 0;4 for (let a = 1; a <= amount; a++) {5 for (const c of coins) {6 if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;7 }8 }9 return best[amount] === Infinity ? -1 : best[amount];10}1fun coinChange(coins: IntArray, amount: Int): Int {2 val best = IntArray(amount + 1) { Int.MAX_VALUE }3 best[0] = 04 for (a in 1..amount) {5 for (c in coins) {6 if (c <= a && best[a - c] != Int.MAX_VALUE && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 17 }8 }9 return if (best[amount] == Int.MAX_VALUE) -1 else best[amount]10}1static int coinChange(int[] coins, int amount) {2 int[] best = new int[amount + 1];3 Arrays.fill(best, Integer.MAX_VALUE);4 best[0] = 0;5 for (int a = 1; a <= amount; a++) {6 for (int c : coins) {7 if (c <= a && best[a - c] != Integer.MAX_VALUE && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;8 }9 }10 return best[amount] == Integer.MAX_VALUE ? -1 : best[amount];11}Step by step
- best[a] = fewest coins for amount a; best[0] = 0.
- Try every coin as the last coin used.
- Still infinite means the amount is unreachable.
Complexity: O(amount × coins) time, O(amount) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
How do you find the state?
Top-down or bottom-up?
How do you reduce memory?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
ways(n) = ways(n-1) + ways(n-2).
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Longest Increasing Subsequence
Length of the longest strictly increasing subsequence, in O(n log n).
- tails[k] = smallest possible tail of an increasing subsequence of length k + 1.
- For each value, binary search where it fits and replace that tail.
- The length of tails is the answer.
1function lengthOfLIS(nums: number[]): number {2 const tails: number[] = [];3 for (const x of nums) {4 let lo = 0, hi = tails.length; // first tail >= x5 while (lo < hi) {6 const mid = (lo + hi) >> 1;7 if (tails[mid] < x) lo = mid + 1;8 else hi = mid;9 }10 tails[lo] = x; // lo === length extends; otherwise lowers a tail11 }12 return tails.length;13}Complexity: O(n log n) time, O(n) space
Edit Distance
Fewest inserts, deletes and replacements to turn word a into word b.
- dp[i][j] = edit distance between the first i letters of a and the first j of b.
- Matching letters cost nothing; otherwise 1 + the best of insert, delete or replace.
1function minDistance(a: string, b: string): number {2 const m = a.length, n = b.length;3 const dp = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));4 for (let i = 0; i <= m; i++) dp[i][0] = i;5 for (let j = 0; j <= n; j++) dp[0][j] = j;6 for (let i = 1; i <= m; i++) {7 for (let j = 1; j <= n; j++) {8 if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];9 else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);10 }11 }12 return dp[m][n];13}Complexity: O(m · n) time and space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Starting to code before stating the state
- Memo keys built from arrays (Map compares them by reference)
- Wrong iteration order in bottom-up tables