/Projects
Coding patterns · 13 of 15

Dynamic programming

Define the state, write the recurrence, fill the table.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot dynamic programming from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(states × transitions) Watch as reels
Part 1 of 5

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.

Why it works

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.

Count the ways / min cost / max valueChoices at each step that affect later stepsOverlapping subproblems in a brute-force recursionStrings compared character by character (LCS, edit distance)
Part 2 of 5

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.

Problem

Fewest coins to make amount; -1 if impossible.

Plan before you code

  1. State: best[a] = fewest coins for amount a.
  2. Recurrence: best[a] = 1 + min(best[a − coin]).
  3. Fill amounts from 1 upwards.
Part 3 of 5

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

topdown-memo.tsTypeScript
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}
10 linesUTF-8TypeScript
  1. State: the cheapest way to finish from step i.
  2. Base case: past the end costs nothing.
  3. 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

coin-change.tsTypeScript
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}
10 linesUTF-8TypeScript

Step by step

  1. best[a] = fewest coins for amount a; best[0] = 0.
  2. Try every coin as the last coin used.
  3. Still infinite means the amount is unreachable.

Complexity: O(amount × coins) time, O(amount) space

Part 4 of 5

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?
Ask what you must know to decide the rest of the problem: usually an index, sometimes plus a remaining amount or a flag.
Top-down or bottom-up?
Top-down mirrors the recurrence and computes only the states it needs; bottom-up avoids deep recursion and makes saving memory easy.
How do you reduce memory?
If each row depends only on the previous row, keep two rows, or one row updated in the right direction.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyClimbing Stairs
Hint

ways(n) = ways(n-1) + ways(n-2).

Part 5 of 5

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
Medium

Longest Increasing Subsequence

Length of the longest strictly increasing subsequence, in O(n log n).

  1. tails[k] = smallest possible tail of an increasing subsequence of length k + 1.
  2. For each value, binary search where it fits and replace that tail.
  3. The length of tails is the answer.
longest-increasing-subsequence.tsTypeScript
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}
13 linesUTF-8TypeScript

Complexity: O(n log n) time, O(n) space

Hard

Edit Distance

Fewest inserts, deletes and replacements to turn word a into word b.

  1. dp[i][j] = edit distance between the first i letters of a and the first j of b.
  2. Matching letters cost nothing; otherwise 1 + the best of insert, delete or replace.
edit-distance.tsTypeScript
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}
13 linesUTF-8TypeScript

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
AI Engineer · Dynamic programming