Skip to content
Velloreth
Programming 8 min read

Dynamic Programming Basics: From Recursion to Tables

Dynamic programming solves problems by caching overlapping subproblems. Learn memoisation, tabulation, and how to spot a DP problem in the wild.

By

What dynamic programming is

Dynamic programming is a technique for solving problems that break into smaller versions of themselves, where those smaller versions repeat. Instead of recomputing them, you compute each once and store the answer.

That is the whole idea. The name is intimidating and historically arbitrary — it has nothing to do with “dynamic” in the usual sense — but the technique is simple.

Two conditions must hold:

  1. Overlapping subproblems — the same smaller problem is solved many times.
  2. Optimal substructure — the optimal answer to the whole is built from optimal answers to the parts.

If the subproblems never repeat, you have plain divide and conquer, and caching adds nothing. If the optimal answer is not built from optimal sub-answers, DP does not apply.

The canonical example: Fibonacci

The Fibonacci sequence is defined recursively: each number is the sum of the two before it.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

This is correct and catastrophically slow. fib(40) makes over a billion function calls, because fib(38) is computed twice, fib(37) three times, and so on. The call tree is exponential: O(2ⁿ).

The problem is that the subproblems overlap. fib(35) is computed thousands of times, always with the same answer.

Memoisation: top-down

Keep the recursion, add a cache.

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

Now each value is computed once and reused. The complexity drops from O(2ⁿ) to O(n). For n = 40, that is 40 computations instead of a billion.

This is the single most dramatic optimisation in introductory computer science, and it is worth internalising: caching turns exponential into linear.

Tabulation: bottom-up

Instead of recursing, build the answer from the smallest case upward.

function fib(n) {
  if (n <= 1) return n;
  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

Same O(n) time, but no recursion and no call stack. And because each value depends only on the previous two, the table can shrink to two variables:

function fib(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

O(n) time, O(1) space. That space reduction is a common and valuable DP refinement.

The two approaches compared

MemoisationTabulation
DirectionTop-downBottom-up
ImplementationRecursion plus cacheIterative table
Ease of derivationEasier — write the recursionHarder — must order the loops
Stack usageO(depth)O(1)
Computes unused statesNoSometimes
Space reductionHarderNatural

Start with memoisation, because it follows directly from the recursive definition. Convert to tabulation once the recurrence is clear and you need the performance.

A worked example: climbing stairs

You are climbing a staircase with n steps. Each move you climb 1 or 2 steps. How many distinct ways are there to reach the top?

The key insight is that to reach step n, you came from step n-1 or step n-2. So the number of ways to reach n is the sum of the ways to reach those two.

function climbStairs(n) {
  if (n <= 2) return n;
  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

This is Fibonacci in disguise. Recognising that a new problem reduces to a known one is a large part of DP skill.

A worked example: coin change

Given coin denominations and a target amount, find the fewest coins that sum to the target.

The state is the amount remaining. The recurrence: the minimum coins for amount a is one plus the minimum for a minus each coin.

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

The table has one entry per amount, and each entry considers every coin. Time is O(amount × coins), space is O(amount).

Notice the structure: dp[a] depends on dp[a - coin], which is a smaller amount. That is why the loop runs upward — every dependency is already computed.

A worked example: 0/1 knapsack

Given items with weights and values, and a capacity, maximise the value you can carry. Each item can be taken at most once.

The state is two-dimensional: which items you have considered, and how much capacity remains.

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // skip item i
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1], // take item i
        );
      }
    }
  }
  return dp[n][capacity];
}

Time is O(n × capacity), space is O(n × capacity). Because row i depends only on row i-1, the space can be reduced to a single row by iterating capacity downward:

function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = capacity; w >= weights[i]; w--) { // downward!
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

The downward iteration is essential. Going upward would allow the same item to be taken multiple times, which is the unbounded knapsack variant. This is a classic trap.

How to approach a DP problem

1. Define the state. What parameters uniquely identify a subproblem? This is the hardest step. For coin change it is the amount. For knapsack it is the item index and remaining capacity. For edit distance it is the two string positions.

2. Write the recurrence. How does the answer for a state relate to smaller states? Express it in terms of the state you defined.

3. Identify the base cases. Which states have trivial answers? Usually the empty input or zero capacity.

4. Determine the order. If you tabulate, which states must be computed first? Every dependency must come earlier.

5. Reduce space if needed. If each row depends only on the previous, keep two rows. If each cell depends on a few neighbours, keep a few variables.

Recognising DP problems

These phrasings usually signal DP:

  • “How many ways…” — counting problems with overlapping structure.
  • “Minimum/maximum cost to…” — optimisation with optimal substructure.
  • “Longest/shortest … subsequence” — sequence alignment.
  • “Can you reach/partition/split…” — feasibility with repeated subproblems.
  • Anything where a greedy choice does not obviously work.

The counter-signal is when subproblems do not repeat. If each subproblem is solved once, you have divide and conquer — merge sort, binary search, quicksort — and caching is pointless.

Common mistakes

Wrong state. If the state does not capture everything the recurrence needs, the answers will be wrong. A missing parameter is the most common DP bug.

Wrong iteration order. In tabulation, computing a state before its dependencies gives garbage. In the knapsack space optimisation, iterating upward silently changes the problem.

Forgetting base cases. An uninitialised table entry propagates wrong values everywhere.

Using memoisation on a non-overlapping problem. It adds overhead and memory for no benefit.

Not reducing space when it matters. An O(n²) table for n = 100,000 is 10 billion entries. The two-row reduction is often the difference between working and not.

Confusing 0/1 and unbounded variants. Whether an item can be reused changes the iteration direction and the answer.

Where DP shows up in practice

  • Diff tools and version control — the longest common subsequence is DP, which is how git diff aligns lines.
  • Spell checkers and autocorrect — edit distance is DP.
  • Bioinformatics — sequence alignment of DNA and proteins.
  • Route planning — shortest paths with constraints.
  • Resource allocation — knapsack variants in scheduling and budgeting.
  • Text justification — optimal line breaking in typesetting.
  • Compression — optimal parsing in some codecs.

For the recursion this builds on, see understanding recursion with practical examples. For the complexity reasoning, Big-O notation explained and time vs space complexity cover the trade-off DP exploits.

Quotable summary

Dynamic programming solves problems with overlapping subproblems and optimal substructure by computing each subproblem once and reusing the answer. Memoisation is top-down, keeping the recursion and caching results; tabulation is bottom-up, filling a table iteratively. Both give the same time complexity, and memoisation is usually easier to derive. Naive Fibonacci is O(2ⁿ) and memoised Fibonacci is O(n), which illustrates the technique’s value. The hardest step is defining the state — the parameters that uniquely identify a subproblem. Space can often be reduced by keeping only the rows a state depends on, and in the 0/1 knapsack that reduction requires iterating capacity downward.

Frequently asked questions

What is dynamic programming in simple terms?
Dynamic programming is a technique for solving problems by breaking them into smaller versions of the same problem and remembering the answers so you never compute the same thing twice. It turns exponential brute force into polynomial time.
What is the difference between memoisation and tabulation?
Memoisation is top-down: you write the natural recursion and cache each result the first time it is computed. Tabulation is bottom-up: you fill a table iteratively from the smallest subproblems upward. Both give the same time complexity; memoisation is easier to derive, tabulation avoids recursion overhead.
How do I know a problem can be solved with dynamic programming?
Two conditions: overlapping subproblems, meaning the same smaller problem is solved many times, and optimal substructure, meaning the optimal answer is built from optimal answers to subproblems. If the subproblems never repeat, plain divide and conquer is enough.
Why is naive Fibonacci so slow?
Because it recomputes the same values exponentially many times. Computing fib(40) makes over a billion calls, most of them duplicates. Caching each result reduces it to 40 computations.
What is the state in dynamic programming?
The state is the set of parameters that uniquely identify a subproblem, such as the index and remaining capacity in the knapsack problem. Choosing the right state is the core skill, because the state determines both the recurrence and the table dimensions.
Can dynamic programming always reduce space complexity?
Often, yes. If each row of the table depends only on the previous row, you can keep two rows instead of all of them, reducing O(n²) space to O(n). Some problems reduce further to O(1) by keeping only a few variables.