Dynamic Programming

Introduction

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems and storing their results so you never solve the same subproblem twice. Think of it like taking notes during a long calculation — instead of redoing work, you look up answers you’ve already figured out.

If you’ve worked through Recursion, you’ve already seen the problem DP solves. Remember the naive recursive Fibonacci? It recalculates the same values over and over. DP eliminates that waste. You’ll also want to be comfortable with Big-O Notation to understand the complexity improvements.

When does DP apply?

A problem is a good candidate for DP when it has two properties:

1. Overlapping Subproblems — The same smaller problems are solved multiple times.

2. Optimal Substructure — The optimal solution to the problem can be built from optimal solutions to its subproblems.

If a problem only has optimal substructure but no overlapping subproblems, you’re looking at plain divide and conquer (like merge sort). If subproblems overlap, DP gives you a speedup.

The Fibonacci problem

Fibonacci is the classic example because it clearly shows both properties. Let’s trace through the naive recursive version:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1
│   │   │   └── fib(0) → 0
│   │   └── fib(1) → 1
│   └── fib(2)
│       ├── fib(1) → 1
│       └── fib(0) → 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) → 1
    │   └── fib(0) → 0
    └── fib(1) → 1

fib(3) is computed twice. fib(2) is computed three times. At fib(40), there are over a billion redundant calls. The time complexity is O(2^n) — unusable for any meaningful input.

Two approaches to DP

Top-Down (Memoization)

Start with the original problem, recurse into subproblems, and cache results as you go. This is the recursive approach with a lookup table bolted on.

Bottom-Up (Tabulation)

Start from the smallest subproblems, build up a table of results, and use them to solve larger subproblems iteratively. No recursion needed.

Both approaches produce the same results. The choice comes down to what feels more natural for the problem.

Fibonacci with DP

Top-Down (Memoization)

function fib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

console.log(fib(6));   // 8
console.log(fib(50));  // 12586269025

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(6))   # 8
print(fib(50))  # 12586269025

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
    public static long fib(int n, Map<Integer, Long> memo) {
        if (memo.containsKey(n)) return memo.get(n);
        if (n <= 1) return n;

        long result = fib(n - 1, memo) + fib(n - 2, memo);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fib(6, new HashMap<>()));   // 8
        System.out.println(fib(50, new HashMap<>()));  // 12586269025
    }
}

Each subproblem is solved once and looked up in O(1) after that. Time: O(n). Space: O(n).

Bottom-Up (Tabulation)

function fib(n) {
  if (n <= 1) return n;

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

console.log(fib(6));   // 8
console.log(fib(50));  // 12586269025

def fib(n):
    if n <= 1:
        return n

    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

print(fib(6))   # 8
print(fib(50))  # 12586269025

public static long fib(int n) {
    if (n <= 1) return n;

    long[] dp = new long[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Same O(n) time, but no recursion overhead and no risk of stack overflow.

Space-Optimized Bottom-Up

Since Fibonacci only depends on the previous two values, we don’t need the full table:

function fib(n) {
  if (n <= 1) return n;

  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

Time: O(n). Space: O(1). This is the optimal solution.

Climbing Stairs

A classic DP 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?

This is Fibonacci in disguise. To reach step n, you either came from step n-1 (one step) or step n-2 (two steps). So ways(n) = ways(n-1) + ways(n-2).

n=1: 1 way   → [1]
n=2: 2 ways  → [1,1], [2]
n=3: 3 ways  → [1,1,1], [1,2], [2,1]
n=4: 5 ways  → [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]

function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

console.log(climbStairs(4));   // 5
console.log(climbStairs(10));  // 89

def climb_stairs(n):
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1

print(climb_stairs(4))   # 5
print(climb_stairs(10))  # 89

public static int climbStairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Time: O(n). Space: O(1).

Minimum Cost Climbing Stairs

Now each step has a cost. Find the minimum cost to reach the top. You can start from step 0 or step 1.

This introduces a key DP pattern: at each step, you make a choice (come from i-1 or i-2) and take the minimum.

Recurrence: dp[i] = cost[i] + min(dp[i-1], dp[i-2])

function minCostClimbingStairs(cost) {
  const n = cost.length;
  let prev2 = cost[0], prev1 = cost[1];

  for (let i = 2; i < n; i++) {
    const current = cost[i] + Math.min(prev1, prev2);
    prev2 = prev1;
    prev1 = current;
  }
  return Math.min(prev1, prev2);
}

console.log(minCostClimbingStairs([10, 15, 20]));        // 15
console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6

def min_cost_climbing_stairs(cost):
    n = len(cost)
    prev2, prev1 = cost[0], cost[1]

    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev2 = prev1
        prev1 = current
    return min(prev1, prev2)

print(min_cost_climbing_stairs([10, 15, 20]))        # 15
print(min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6

public static int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int prev2 = cost[0], prev1 = cost[1];

    for (int i = 2; i < n; i++) {
        int current = cost[i] + Math.min(prev1, prev2);
        prev2 = prev1;
        prev1 = current;
    }
    return Math.min(prev1, prev2);
}

Time: O(n). Space: O(1).

House Robber

You’re a robber planning to rob houses along a street. Each house has a certain amount of money, but you can’t rob two adjacent houses (alarm system). Find the maximum amount you can rob.

Recurrence: At each house, you either rob it (add its value to the best you could do two houses back) or skip it (keep the best from the previous house).

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

function rob(nums) {
  if (nums.length === 1) return nums[0];

  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);

  for (let i = 2; i < nums.length; i++) {
    const current = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

console.log(rob([1, 2, 3, 1]));     // 4 (rob house 0 and 2)
console.log(rob([2, 7, 9, 3, 1]));  // 12 (rob house 0, 2, and 4)

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current
    return prev1

print(rob([1, 2, 3, 1]))     # 4
print(rob([2, 7, 9, 3, 1]))  # 12

public static int rob(int[] nums) {
    if (nums.length == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        int current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Time: O(n). Space: O(1).

How to approach a DP problem

Here’s a framework that works for most DP problems:

1. Define the subproblem. What does dp[i] (or dp[i][j]) represent? State this clearly in words before writing any code.

2. Find the recurrence relation. How does dp[i] relate to smaller subproblems? This is the core of the solution.

3. Identify the base cases. What are the smallest subproblems you can solve directly?

4. Determine the computation order. For bottom-up, make sure you compute subproblems before you need them.

5. Optimize space if possible. If dp[i] only depends on the last few values, you don’t need the full table.

Top-Down vs Bottom-Up

In interviews, start with whichever feels more natural. If the interviewer asks for optimization, convert to bottom-up and then reduce space.

Complexity analysis

DP transforms problems from exponential to polynomial time:

The space complexity depends on the number of dimensions in your DP table and whether you can optimize it.

Practice problems

1. Climbing Stairs (1, 2, or 3 steps variant)
2. Coin Change — minimum coins to make amount
3. Longest Increasing Subsequence
4. Maximum Subarray (Kadane’s Algorithm)
5. Unique Paths in a grid
6. 0/1 Knapsack Problem
7. Longest Common Subsequence
8. Edit Distance
9. Word Break
10. Decode Ways

Dynamic programming is a skill that improves with practice. The patterns repeat — once you’ve solved a few problems in each category (1D, 2D, string DP, decision-making), new problems start to feel familiar. Start with the examples in this tutorial, then work through the practice problems above.