Dynamic Programming: Intro Patterns

When recursion keeps solving the same subproblem again and again, remember the answers once. That one trick turns exponential Fibonacci into linear time on exam questions.

Class 11 to 12advanced45 min4 lessons

By the end you will be able to

Identify overlapping subproblems and optimal substructure
Convert a naive recursion into a memoised one
Rewrite a memoised solution as a bottom-up table
Reduce a table to O(1) space when only the last rows matter

Finish first

Recursion: Functions That Call Themselves Complexity & Big-O Arrays

Cost at a glance

naiveFibonacci: O(2ⁿ)
memoised: O(n) time, O(n) space
tabulated: O(n) time, O(n) space
rolling: O(n) time, O(1) space
coinChange: O(amount × coins)

Topic contents

Lesson 1 of 4

The same work, over and over

Write Fibonacci as the textbook recursion and it is correct but ruinous: fib(50) makes over 20 billion calls. Draw the call tree and the reason is obvious. fib(5) needs fib(4) and fib(3); fib(4) also needs fib(3). That shared subtree is recomputed from scratch every time it is reached, and the duplication compounds at every level.

This is the first of the two conditions that make dynamic programming apply: overlapping subproblems, meaning the same subproblem is solved repeatedly. The second is optimal substructure, meaning the answer to a problem can be assembled from answers to its subproblems. When both hold, you can solve each subproblem once, remember the answer, and reuse it.

Dynamic programming is not an algorithm, it is that one idea. The names attached to it, memoisation and tabulation, are simply two ways to do the remembering.

Continue

Lesson 2 of 4

Memoisation: top down

Memoisation keeps the recursion exactly as written and adds a cache in front of it. On entry, check whether this input has been solved before and return the stored answer if so; otherwise compute it, store it, and return. The structure of the code barely changes, which is what makes this the easiest first step.

The effect on complexity is dramatic and easy to justify. There are n distinct inputs, each is computed once, and each computation does constant work beyond its recursive calls, so the total is O(n) time with O(n) space for the cache. The exponential blow-up came entirely from repetition, and the cache removes the repetition.

Watch it happen

Memoised Fibonacci, call by call

Watch the cache fill. After the first descent, every later call is answered without any recursion at all.

javascriptline 9

const memo = new Map();
function fib(n) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fib(n - 1) + fib(n - 2);
memo.set(n, result);
return result;
}
fib(5);

Variables now

memo: {}

Output

Nothing printed yet.

1 / 7

Line 9

fib(5) is called. The cache is empty, so the recursion has to descend.

Continue

Lesson 3 of 4

Tabulation: bottom up

Tabulation turns the recursion inside out. Instead of asking for fib(n) and letting it descend, you fill a table from the base cases upwards until the answer you want is in it. There is no recursion, so there is no call stack to overflow, and the loop order makes the dependencies explicit: each entry is computed only after the entries it depends on.

Once the table exists, look at what each row actually needs. Fibonacci needs only the previous two values, so the whole table can collapse into two variables and the space drops from O(n) to O(1). This reduction is extremely common in dynamic programming: a grid problem that only reads the row above can keep one row instead of the whole grid.

Watch it happen

Memoisation against tabulation

Same complexity, different trade-offs. One row at a time.

Memoisation

top down, recursive, cached

1 win

Tabulation

bottom up, iterative, table

0 wins

Code shape
The naive recursion plus a cache check
A rewrite as loops over a table
Subproblems solved
Only the ones actually reached
Every entry in the table
Stack depth
O(n), can overflow on deep inputs
None, it is a loop
Space reduction
Hard, the cache is accessed unpredictably
Easy, drop rows once nothing needs them
Best first move
Yes, start here to get correct fast
Convert once it works and the shape is clear

1 / 5

Code shape

Code shape: Memoisation wins here: The naive recursion plus a cache check against A rewrite as loops over a table.

Continue

Lesson 4 of 4

The patterns worth recognising

Climbing stairs: you can take 1 or 2 steps, so the number of ways to reach step n is the ways to reach n-1 plus the ways to reach n-2. It is Fibonacci wearing a costume, and spotting that is the skill being trained.

Coin change and 0/1 knapsack: for each item, either take it or leave it, and the answer is the better of those two branches. The table is indexed by item and by remaining capacity, and each cell asks that same one question.

Longest common subsequence and edit distance: a two-dimensional table over the two strings, where each cell compares one character from each and either extends a match or takes the best of skipping one side. This is the machinery behind `git diff` and spell checkers.

The recurring method is worth stating plainly. Define what the subproblem means in words, write the recurrence that relates it to smaller subproblems, identify the base cases, then choose top down or bottom up. Getting the definition of the subproblem precise is where most of the difficulty lives; once it is stated exactly, the recurrence usually follows in a line or two.

Continue

Worked examples

Read the code, then change it

Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.

Three Fibonaccis, measuredJavaScript

let naiveCalls = 0;
function naive(n) {
  naiveCalls += 1;
  return n <= 1 ? n : naive(n - 1) + naive(n - 2);
}

function memoised(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = memoised(n - 1, memo) + memoised(n - 2, memo);
  memo.set(n, result);
  return result;
}

// Bottom up, and then the O(1) space version.
function tabulated(n) {
  const table = [0, 1];
  for (let i = 2; i <= n; i += 1) table[i] = table[i - 1] + table[i - 2];
  return table[n];
}

function rolling(n) {
  let previous = 0;
  let current = 1;
  for (let i = 2; i <= n; i += 1) {
    const next = previous + current;
    previous = current;
    current = next;
  }
  return n <= 1 ? n : current;
}

console.log('naive(30)     =', naive(30), 'in', naiveCalls, 'calls');
console.log('memoised(30)  =', memoised(30));
console.log('tabulated(30) =', tabulated(30));
console.log('rolling(30)   =', rolling(30), '(O(1) space)');
console.log('rolling(90)   =', rolling(90), '(naive would never finish)');

Coin change: fewest coinsJavaScript

// Subproblem, stated in words: best[a] is the fewest coins that make amount a.
function fewestCoins(coins, amount) {
  const best = new Array(amount + 1).fill(Infinity);
  best[0] = 0; // base case: zero coins make zero

  for (let a = 1; a <= amount; a += 1) {
    for (const coin of coins) {
      if (coin <= a && best[a - coin] + 1 < best[a]) {
        best[a] = best[a - coin] + 1;
      }
    }
  }
  return best[amount] === Infinity ? -1 : best[amount];
}

console.log(fewestCoins([1, 5, 10, 25], 63)); // 6: 25+25+10+1+1+1
console.log(fewestCoins([2], 3));             // -1: impossible

// Greedy fails here, DP does not:
console.log(fewestCoins([1, 3, 4], 6));       // 2 (3+3), greedy would say 3 (4+1+1)

Practice

Work these out yourself

No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.

0/5 attempted

Finished this topic?

0 of 4 lessons marked done. Marking the topic complete ticks the rest.

The same work, over and over

Memoisation: top down

Tabulation: bottom up

The patterns worth recognising

Read the code, then change it

Work these out yourself

Check your understanding

Finished this topic?