Dynamic Programming

1. What is Dynamic Programming?

Dynamic Programming (DP) is a technique for solving problems by breaking them into overlapping subproblems and storing the results so you never solve the same subproblem twice. That is literally all it is.

For a problem to be solvable with DP, it needs two key properties:

1. Optimal substructure -- the optimal solution to the problem contains optimal solutions to its subproblems. If you can build the answer from answers to smaller versions of the same problem, you have this.
2. Overlapping subproblems -- the same subproblems are solved multiple times. This is why storing results helps. If each subproblem is unique (like in merge sort), DP won't help -- that is just divide and conquer.

Why naive recursion is slow

Consider computing Fibonacci(5). A naive recursive approach recalculates the same values over and over:

/*
                     fib(5)
                   /        \
              fib(4)         fib(3)
             /    \          /    \
         fib(3)  fib(2)  fib(2)  fib(1)
         /   \    / \     / \
     fib(2) fib(1) ...  ...
      / \
 fib(1) fib(0)

 fib(3) is computed 2 times
 fib(2) is computed 3 times
 This EXPLODES exponentially as n grows
*/

With DP, you compute each value once, store it, and look it up next time. That takes you from O(2^n) to O(n).

2. Top-Down (Memoization) vs Bottom-Up (Tabulation)

There are two ways to implement DP. Both give the same results -- they just approach the problem from different directions.

Top-Down (Memoization)

• Start from the original problem and recurse downward
• Cache (memoize) results of subproblems as you go
• Easier to think about -- just write the recursive solution and add a cache
• May have recursion overhead (stack frames)

Bottom-Up (Tabulation)

• Start from the smallest subproblems and build up iteratively
• Fill a table (array) from base cases to final answer
• No recursion overhead -- pure iteration
• Can be more efficient in practice
• Sometimes easier to optimize space

3. The DP Problem-Solving Framework

Use this 5-step framework for every DP problem. Seriously -- every single one.

4. Fibonacci (The Classic Intro)

Every DP tutorial starts with Fibonacci for a reason: it perfectly illustrates why DP exists. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, ... where each number is the sum of the two before it.

Approach 1: Naive Recursion -- O(2^n) time, O(n) space

This is what NOT to do. Each call branches into two more, creating exponential work.

Python
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(40) takes SECONDS. fib(50) may never finish.

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

Approach 2: Top-Down with Memoization -- O(n) time, O(n) space

Same recursion, but we remember every result. Each fib(k) is computed exactly once.

Python
def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

# fib(1000) returns instantly

JavaScript
function fib(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n] !== undefined) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

Approach 3: Bottom-Up Tabulation -- O(n) time, O(n) space

Build the table iteratively from the base cases up. No recursion at all.

Python
def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

JavaScript
function fib(n) {
    if (n <= 1) return n;
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Approach 4: Space-Optimized -- O(n) time, O(1) space

We only ever look at the last two values, so why store the whole array?

Python
def fib(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

JavaScript
function fib(n) {
    if (n <= 1) return n;
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

5. Climbing Stairs

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

Wait -- this is just Fibonacci! To reach step i, you either came from step i-1 (one step) or step i-2 (two steps). The total ways is the sum of both.

Top-Down

Python
def climbStairs(n, memo={}):
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    return memo[n]

JavaScript
function climbStairs(n, memo = {}) {
    if (n <= 1) return 1;
    if (memo[n] !== undefined) return memo[n];
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    return memo[n];
}

Bottom-Up (Space-Optimized)

Python
def climbStairs(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

JavaScript
function climbStairs(n) {
    if (n <= 1) return 1;
    let prev2 = 1, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

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

6. 1D DP Problems

House Robber

Problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money. You cannot rob two adjacent houses (alarm triggers). Find the maximum amount you can rob.

At each house, you have two choices: skip it (take dp[i-1]) or rob it (take dp[i-2] + this house's money). Pick whichever is more.

Top-Down

Python
def rob(nums):
    memo = {}
    def dp(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]
        memo[i] = max(dp(i - 1), dp(i - 2) + nums[i])
        return memo[i]
    return dp(len(nums) - 1)

JavaScript
function rob(nums) {
    const memo = {};
    function dp(i) {
        if (i < 0) return 0;
        if (memo[i] !== undefined) return memo[i];
        memo[i] = Math.max(dp(i - 1), dp(i - 2) + nums[i]);
        return memo[i];
    }
    return dp(nums.length - 1);
}

Bottom-Up (Space-Optimized)

Python
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = 0, 0
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = curr
    return prev1

JavaScript
function rob(nums) {
    let prev2 = 0, prev1 = 0;
    for (const num of nums) {
        const curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

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

Maximum Subarray (Kadane's Algorithm)

Problem: Find the contiguous subarray with the largest sum.

At each element, you decide: start a new subarray here, or extend the previous one. If the running sum is negative, start fresh.

Python
def maxSubArray(nums):
    max_sum = curr_sum = nums[0]
    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)
    return max_sum

JavaScript
function maxSubArray(nums) {
    let maxSum = nums[0], currSum = nums[0];
    for (let i = 1; i < nums.length; i++) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
}

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

Coin Change

Problem: Given coin denominations and a target amount, find the minimum number of coins needed. If impossible, return -1.

Top-Down

Python
def coinChange(coins, amount):
    memo = {}
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]
        memo[remaining] = min(dp(remaining - c) + 1 for c in coins)
        return memo[remaining]

    result = dp(amount)
    return result if result != float('inf') else -1

JavaScript
function coinChange(coins, amount) {
    const memo = {};
    function dp(remaining) {
        if (remaining === 0) return 0;
        if (remaining < 0) return Infinity;
        if (memo[remaining] !== undefined) return memo[remaining];
        let min = Infinity;
        for (const coin of coins) {
            min = Math.min(min, dp(remaining - coin) + 1);
        }
        memo[remaining] = min;
        return min;
    }
    const result = dp(amount);
    return result === Infinity ? -1 : result;
}

Bottom-Up

Python
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

JavaScript
function 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] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

Time: O(amount * coins) | Space: O(amount)

Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest strictly increasing subsequence (not necessarily contiguous).

Python
def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

JavaScript
function lengthOfLIS(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
}

Time: O(n^2) | Space: O(n)

7. 2D DP Problems

When your state depends on two variables (two indices, a position in a grid, etc.), you need a 2D DP table.

Unique Paths

Problem: Given an m x n grid, starting at top-left, you can only move right or down. How many unique paths to the bottom-right?

Python
def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

JavaScript
function uniquePaths(m, n) {
    const dp = Array.from({ length: m }, () =>
        new Array(n).fill(1)
    );
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

Time: O(m * n) | Space: O(m * n), can be optimized to O(n) using a single row

Longest Common Subsequence (LCS)

Problem: Given two strings, find the length of their longest common subsequence.

Python
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

JavaScript
function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () =>
        new Array(n + 1).fill(0)
    );
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Time: O(m * n) | Space: O(m * n)

0/1 Knapsack

Problem: Given items with weights and values, and a knapsack with weight capacity W, maximize the total value you can carry. Each item can only be used once.

Python
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

JavaScript
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++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

Time: O(n * W) | Space: O(n * W), can be optimized to O(W) using a 1D array

8. DP Categories Cheat Sheet

Most DP problems fall into one of these categories. Recognizing the category is half the battle.

9. LeetCode Problems by Category

1D DP

2D DP

Classic Patterns

10. Tips for DP

• 1
  If you can solve it recursively, you can DP it. Every DP problem has a recursive brute-force solution. Start there, identify overlapping subproblems, add memoization. Done.
• 2
  Draw the recursion tree. Literally sketch it on paper. You will SEE the overlapping subproblems. This also helps you identify the state and recurrence.
• 3
  Start with brute force, then optimize. Don't try to jump straight to the DP solution. Write the recursive solution first. Then add memoization. Then convert to bottom-up if needed. Then optimize space.
• 4
  Practice identifying the state and recurrence. For every problem, ask: "What does dp[i] represent?" and "How does dp[i] relate to smaller subproblems?" These two questions are the entire game.
• 5
  Most DP problems are variations of ~10 core patterns. Fibonacci, knapsack, LCS, LIS, grid paths, interval DP, tree DP, bitmask DP, digit DP, and state machine DP. Learn these and you can solve almost anything.

11. Practice Quiz