Dynamic Programming Fundamentals: Stop Being Scared of It

DP has a reputation that it doesn't fully deserve. Ask most engineers what they dread most in a technical interview and they'll say "dynamic programming" in the same tone someone uses for "root canal." That's because it gets taught the wrong way — as some magic black box where you somehow divine the right recurrence relation, and if you don't see it immediately, you've failed.

Here's the actual truth: DP is a pattern, not a superpower. Once you see what makes a problem DP-able and learn a systematic way to approach it, the scary reputation falls apart pretty fast. This article walks through three classic problems — Climbing Stairs, House Robber, and Coin Change — with every approach shown explicitly, from naive recursion all the way to space-optimized tabulation.

The Two Things That Make a Problem "DP"

Every DP problem has two structural properties. If a problem doesn't have both of them, DP won't help.

Overlapping subproblems — you end up solving the same smaller problem multiple times. Naive recursion recomputes these repeatedly, wasting exponential time. Memoization or tabulation fixes this by caching results.

Optimal substructure — the optimal solution to the whole problem can be built from optimal solutions to its subproblems. This is what lets you define a clean recurrence.

That's it. That's the whole theory. The rest is just practice recognizing the pattern and translating it into code.

Problem 1: Climbing Stairs (LeetCode 70)

The problem: You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

Why This Is DP

To reach step n, you either came from step n-1 (took 1 step) or step n-2 (took 2 steps). The number of ways to reach n is the sum of ways to reach those two previous steps. That's your recurrence, and it naturally produces overlapping subproblems.

Here's what the recursion tree looks like for n = 5:

See those orange and red nodes? climb(3) gets computed twice, climb(2) gets computed three times. At larger inputs this explodes. For n = 40 you'd be doing hundreds of millions of redundant calls.

Approach 1: Brute Force (Naive Recursion)

// Brute force — O(2^n) time, O(n) space (call stack)
const climbStairs = (n) => {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
};

This is correct but completely impractical. The base cases are n=1 (one way: take one step) and n=2 (two ways: 1+1 or 2). Everything else is just the Fibonacci recurrence in disguise.

Approach 2: Memoization (Top-Down DP)

Fix the brute force by caching results. If we've already computed climbStairs(k), store it and return immediately instead of recomputing.

// Memoization — O(n) time, O(n) space
const climbStairsMemo = (n, memo = {}) => {
  if (n <= 2) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
  return memo[n];
};

The default parameter memo = {} lets the top-level caller pass nothing, while recursive calls share the same object. This is O(n) time because each value from 1 to n gets computed exactly once.

Approach 3: Tabulation (Bottom-Up DP)

Flip the direction. Instead of starting at n and recursing down, start from the base cases and build up. This trades recursion depth concerns for a simple loop.

// Tabulation — O(n) time, O(n) space
const climbStairsDP = (n) => {
  if (n <= 2) return n;
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

dp[i] stores the number of ways to reach step i. We fill the table left to right and read off the answer at the end. Same O(n) time and space as memoization, but no call stack overhead.

Approach 4: Space-Optimized

At any point in the loop, we only ever look at the last two values. We don't need the whole table.

// Space-optimized — O(n) time, O(1) space
const climbStairsOpt = (n) => {
  if (n <= 2) return n;
  let [prev2, prev1] = [1, 2];
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
};

This is essentially computing Fibonacci numbers with two rolling variables. O(1) space. In an interview, if you can get here after showing the full tabulation approach first, you're doing great.

Problem 2: House Robber (LeetCode 198)

The problem: You're a robber hitting houses along a street. Each house has some amount of money. You can't rob two adjacent houses (alarm triggers). Find the maximum amount you can rob.

Defining the State

This is where DP thinking really matters. Get the state definition wrong and everything falls apart.

Let dp[i] = the maximum money you can rob from the first i+1 houses (index 0 through i).

At each house i, you make a binary choice:

• Skip house i: take whatever the best was through i-1, so dp[i-1]
• Rob house i: you can't have robbed i-1, so take the best through i-2 plus nums[i], so dp[i-2] + nums[i]

That gives the recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

// Brute force — O(2^n) time, O(n) space (call stack)
const rob = (nums) => {
  const helper = (i) => {
    if (i < 0) return 0;
    return Math.max(helper(i - 1), helper(i - 2) + nums[i]);
  };
  return helper(nums.length - 1);
};
 
// Memoization — O(n) time, O(n) space
const robMemo = (nums) => {
  const memo = new Array(nums.length).fill(-1);
  const helper = (i) => {
    if (i < 0) return 0;
    if (memo[i] !== -1) return memo[i];
    memo[i] = Math.max(helper(i - 1), helper(i - 2) + nums[i]);
    return memo[i];
  };
  return helper(nums.length - 1);
};
 
// Tabulation — O(n) time, O(n) space
const robDP = (nums) => {
  const { length } = nums;
  if (length === 0) return 0;
  if (length === 1) return nums[0];
  const dp = new Array(length);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[length - 1];
};
 
// Space-optimized — O(n) time, O(1) space
const robOpt = (nums) => {
  const { length } = nums;
  if (length === 0) return 0;
  if (length === 1) return nums[0];
  let [prev2, prev1] = [nums[0], Math.max(nums[0], nums[1])];
  for (let i = 2; i < length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
};

Walking Through an Example

For nums = [2, 7, 9, 3, 1]:

Answer: 12 (rob houses 0, 2, 4 → 2 + 9 + 1 = 12).

The key insight: the "state" represents the best you can do up to and including position i, considering every possible subset of non-adjacent houses up to that point. You never need to think about which specific houses get robbed — just track the running maximum.

Problem 3: Coin Change (LeetCode 322)

The problem: Given coin denominations and an amount, find the minimum number of coins needed to make that amount. If it's impossible, return -1.

This one is structurally different from the first two. It's an unbounded knapsack pattern — you can use each coin denomination as many times as you want, and you want to minimize the count.

Defining the State

dp[amount] = the minimum number of coins needed to make exactly that amount.

For each amount from 1 to the target, and for each coin denomination, if coin <= amount, then using that coin leaves you with a subproblem of amount - coin. The recurrence:

dp[i] = min(dp[i], dp[i - coin] + 1) for all coins where coin <= i

Initialize dp[0] = 0 (zero coins to make zero money) and everything else to Infinity (impossible until proven otherwise).

// Brute force — O(n^(S/m)) time, O(S/m) space
// n = coins.length, S = amount, m = smallest coin. The recursion tree branches n ways
// and is at most S/m deep, so the cost is exponential in the amount, not in the coin count.
const coinChangeBrute = (coins, amount) => {
  const helper = (remaining) => {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    let minCoins = Infinity;
    for (const coin of coins) {
      const result = helper(remaining - coin);
      if (result !== Infinity) {
        minCoins = Math.min(minCoins, result + 1);
      }
    }
    return minCoins;
  };
  const result = helper(amount);
  return result === Infinity ? -1 : result;
};
 
// Memoization — O(S * n) time, O(S) space
const coinChangeMemo = (coins, amount) => {
  const memo = new Map();
  const helper = (remaining) => {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining);
    let minCoins = Infinity;
    for (const coin of coins) {
      const result = helper(remaining - coin);
      if (result !== Infinity) {
        minCoins = Math.min(minCoins, result + 1);
      }
    }
    memo.set(remaining, minCoins);
    return minCoins;
  };
  const result = helper(amount);
  return result === Infinity ? -1 : result;
};
 
// Tabulation — O(S * n) time, O(S) space
const coinChange = (coins, amount) => {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

Building the Table

Here's how dp fills out for coins = [1, 5, 6, 9], amount = 11:

At dp[11]: try coin 1 → dp[10] + 1 = 3. Try coin 5 → dp[6] + 1 = 2. Try coin 6 → dp[5] + 1 = 2. Try coin 9 → dp[2] + 1 = 3. Minimum is 2 (use a 5 and a 6).

Why "Unbounded Knapsack"

In the classic 0/1 knapsack, each item can only be used once. Here, each coin can be used unlimited times. The practical difference in the DP: you iterate amounts in the outer loop and coins in the inner loop (not the other way around, and no "marking" a coin as used). Each dp[i] subproblem independently decides which coins to use.

Interview Tips: The DP Framework

When you see a DP problem in an interview and your brain wants to freeze, run through this four-step checklist:

1. Define the state explicitly. Don't just say "dp[i] is something about the input up to i." Be precise: "dp[i] is the maximum profit achievable using items 0 through i." Write it out. This forces clarity and often reveals the recurrence directly.

2. Write the recurrence before touching code. dp[i] = max(dp[i-1], dp[i-2] + nums[i]) should appear in your explanation before any code does. If you can't verbalize the recurrence, you don't understand the problem yet.

3. Get the base cases right. This is where most bugs live. Ask yourself: what's the smallest valid input? Does dp[0] need special-casing? Does dp[1]? Enumerate these explicitly.

4. Code it bottom-up. Memoization is fine and sometimes easier to reason about, but interviewers tend to prefer tabulation because it's iterative and easier to trace through by hand. Once you have tabulation working, offer the space optimization as a follow-up.

A few more things worth knowing:

• Say the brute force out loud first. "The naive approach is just recursion trying every option, which is exponential. The insight is that we're recomputing the same subproblems, so we cache them." This shows you understand why DP is the right tool.

• 1D vs 2D DP: If the problem has one changing variable (amount, step count, house index), you probably need a 1D table. If it has two (item count and capacity, or two string lengths), you need 2D. Recognize this early.

• "Minimum/maximum" + "counting paths" or "choices across items" → think DP. Especially when a greedy approach would break on counter-examples. Coin Change is the classic example where greedy (always pick the largest coin) fails for certain denominations.

• Don't over-engineer the state. New DP learners sometimes define state with too many dimensions. Start simple: what's the minimum information you need to fully describe where you are in the problem? Usually it's one or two integers.

The pattern across all three problems here is the same: identify that choices at each step reduce to smaller identical problems, write down what "optimal for size k" means, figure out how it depends on size k-1, nail the base cases, and code it up. The only thing that changes problem to problem is what the state represents and what the transition looks like.

Practice enough problems and you stop seeing DP as scary — you start seeing it as a reliable tool you know how to pick up and use.