Classic DP Problems

Written by Swapnil RajaPublished 28 Aug 2026

Most DP questions are one of four problems wearing different clothes. Learn these and you will start recognising the shape rather than solving from scratch.

1. Climbing stairs - counting ways

You can climb 1 or 2 steps at a time. How many ways to reach step n? The answer for step n is the sum of the ways to reach the two steps you could have come from.

Counting paths

javascript

function climbStairs(n) {
  let twoBack = 1
  let oneBack = 1

  for (let i = 2; i <= n; i++) {
    ;[twoBack, oneBack] = [oneBack, oneBack + twoBack]
  }

  return oneBack
}

console.log(climbStairs(5))  // 8

PreviousDynamic Programming Explained Next1D Dynamic Programming

Minimum coins

javascript

function coinChange(coins, amount) {
  // best[i] = fewest coins to make i. Infinity means impossible.
  const best = new Array(amount + 1).fill(Infinity)
  best[0] = 0

  for (let total = 1; total <= amount; total++) {
    for (const coin of coins) {
      if (coin <= total && best[total - coin] + 1 < best[total]) {
        best[total] = best[total - coin] + 1
      }
    }
  }

  return best[amount] === Infinity ? -1 : best[amount]
}

console.log(coinChange([1, 5, 10, 25], 30))  // 2
console.log(coinChange([5], 3))              // -1

0/1 knapsack

javascript

function knapsack(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0)

  for (let i = 0; i < weights.length; i++) {
    // Downwards, so each item is used at most once.
    for (let c = capacity; c >= weights[i]; c--) {
      best[c] = Math.max(best[c], best[c - weights[i]] + values[i])
    }
  }

  return best[capacity]
}

console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))  // 9

Classic DP Problems

1. Climbing stairs - counting ways

2. Coin change - fewest to reach a total

3. Longest common subsequence - comparing sequences

4. Knapsack - choosing under a limit

Recognising which is which