Part 6 · 2 chapters · ~12 min

Dynamic Programming

Recognising overlapping subproblems and optimal substructure, the five-step method (state, recurrence, base case, order, answer), memoisation versus tabulation, classic problems (coin change, knapsack, longest common subsequence, edit distance), space optimisation, and reconstructing solutions.

The method

code

// coin change: fewest notes, bottom-up
function minNotes(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity); dp[0] = 0;
  for (let x = 1; x <= amount; x++) for (const c of coins) if (c <= x && dp[x - c] + 1 < dp[x]) dp[x] = dp[x - c] + 1;
  return dp[amount] === Infinity ? -1 : dp[amount];
}
minNotes([200, 500, 1000], 1500);   // 2
minNotes([1, 3, 4], 6);             // 2 (3 + 3), where greedy gives 3 (4 + 1 + 1)

DYNAMIC PROGRAMMING, STEP BY STEP

minimum notes to pay ₦1,500 with ₦200, ₦500 and ₦1,000 notes... and why greedy can fail

swipe the figure sideways, or tap expand for full screen

1/5

the state

Dynamic programming applies when a problem breaks into overlapping subproblems with optimal substructure. Define what one subproblem is: the fewest notes to make amount x.

name the subproblem preciselydp[x] = fewest notes for x

Classic problems

problem	state	use in practice
0/1 knapsack	dp[i][w] = best value with first i items and capacity w	choosing loans to fund under a capital limit
longest common subsequence	dp[i][j] over prefixes of two strings	diff tools, reconciliation of sequences
edit distance (Levenshtein)	dp[i][j] = edits to turn prefix i into prefix j	fuzzy matching of names ("Adeniji" vs "Adenji") in KYC and reconciliation
longest increasing subsequence	dp[i] or patience sorting in O(n log n)	trend detection
interval scheduling with weights	dp over sorted end times + binary search	booking and scheduling

code

// edit distance with one row of memory
function editDistance(a: string, b: string): number {
  let prev = Array.from({ length: b.length + 1 }, (_, j) => j);
  for (let i = 1; i <= a.length; i++) {
    const cur = [i];
    for (let j = 1; j <= b.length; j++) cur[j] = Math.min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1));
    prev = cur;
  }
  return prev[b.length];
}
editDistance('Adeniji', 'Adenji');   // 1