Dynamic programming for beginners

Dynamic programming (DP) solves a problem by breaking it into smaller overlapping subproblems, solving each once, and reusing the answers. It turns many exponential recursive solutions into polynomial ones.

When does DP apply?

Look for two properties:

Overlapping subproblems: the same smaller question is asked many times.
Optimal substructure: the best answer for the whole is built from the best answers of the parts.

Typical wording: "how many ways", "minimum cost", "maximum value", "is it possible", "longest/shortest sequence".

A repeatable method

Define the state: what does dp[i] (or dp[i][j]) mean, in plain words?
Write the recurrence: how does a state depend on smaller states?
Set the base cases.
Choose the order: top-down with memoization, or bottom-up with a table.
Find the answer: which state holds it?
Optimise space if the recurrence only looks back a few states.

Example 1: climbing stairs

You can climb 1 or 2 steps at a time. How many ways to reach step n?

State: dp[i] = number of ways to reach step i.
Recurrence: the last move came from i - 1 or i - 2, so dp[i] = dp[i-1] + dp[i-2].
Base: dp[0] = 1, dp[1] = 1.

function climbStairs(n) {
  let a = 1, b = 1;                     // dp[i-2], dp[i-1]
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// Time O(n), space O(1)

It is the Fibonacci sequence. Only the last two values are needed, so two variables replace the table.

Top-down (memoization) vs bottom-up (tabulation)

Top-down: write the natural recursion, then cache results.

function climb(n, memo = {}) {
  if (n <= 1) return 1;
  if (memo[n]) return memo[n];
  return (memo[n] = climb(n - 1, memo) + climb(n - 2, memo));
}

Easier to write, only computes needed states.
Uses recursion depth, which can overflow for huge n.

Bottom-up: fill a table from the smallest states upward.

No recursion, usually faster, and easy to space-optimise.
You must decide the correct fill order.

Example 2: coin change (minimum coins)

Given coin values and an amount, find the fewest coins that make the amount, or -1.

State: dp[a] = fewest coins to make amount a.
Recurrence: dp[a] = 1 + min(dp[a - coin]) over all coins that fit.
Base: dp[0] = 0; others start at infinity.

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

A greedy approach (always take the biggest coin) can fail for some coin sets, which is why DP is needed.

Example 3: 0/1 knapsack

Each item has a weight and a value. Choose items to maximise value within a weight limit, using each item at most once.

State: dp[i][w] = best value using the first i items with capacity w.
Recurrence: skip the item, or take it if it fits: dp[i][w] = max(dp[i-1][w], value + dp[i-1][w - weight]).

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--) {          // go downward so each item is used once
      dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
    }
  }
  return dp[capacity];
}
// Time O(n * capacity), space O(capacity)

The 1D version loops capacity downward to avoid using an item twice. Looping upward gives the unbounded knapsack instead.

Common DP families

1D sequences: climbing stairs, house robber, maximum subarray, decode ways, longest increasing subsequence.
Grids: unique paths, minimum path sum.
Two strings: longest common subsequence, edit distance.
Knapsack-like: subset sum, partition equal subset, coin change.
Intervals and partitions: palindromic substrings, matrix chain (harder).

Example pattern: two strings (edit distance idea)

State dp[i][j] is the answer for the first i characters of A and the first j of B. The recurrence looks at the last characters: if equal, carry over dp[i-1][j-1]; otherwise take the best of insert, delete or replace plus one.

Tips for interviews

Start with the brute-force recursion, state its complexity, then say "the same subproblems repeat, so I will cache them".
Say what the state means out loud. Most mistakes are an unclear state.
Draw a small table by hand to check the recurrence.
Mention space optimisation after a correct solution.
If you cannot see DP, ask whether greedy or sorting gives a simpler answer.

Common mistakes

A state that does not capture enough information to decide the next step.
Wrong base cases or off-by-one indexes.
Wrong loop order (especially in knapsack).
Using DP where the number of states is too large.
Forgetting that memoization keys must include all changing parameters.

Practice problems

Climbing Stairs, House Robber, Maximum Subarray, Coin Change, Longest Increasing Subsequence, Unique Paths, Longest Common Subsequence, Partition Equal Subset Sum, Edit Distance.

Takeaway: define the state, write the recurrence, set base cases, and cache or tabulate. Start from a recursive solution, then optimise.

Interview prep and DSA series, Part 2 (data structures and behaviour): 4 of 5. Previous: Graphs, BFS and DFS: how to solve graph interview problems.

Dynamic programming for beginners: a step-by-step method