Dynamic Programming

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into simpler subproblems. It works when problems have overlapping subproblems and optimal substructure.

When to Use DP

1. Overlapping Subproblems: Same subproblems are solved multiple times
2. Optimal Substructure: Optimal solution can be built from optimal solutions of subproblems

Common signals:

• “Find the minimum/maximum…”
• “Count the number of ways…”
• “Is it possible to…”
• “Find the longest/shortest…”

Two Approaches

Top-Down (Memoization)

Start from the main problem, recursively solve subproblems, cache results.

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

Bottom-Up (Tabulation)

Start from smallest subproblems, build up to main problem.

def fib_tab(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]

# Space optimized
def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

DP Problem-Solving Framework

1. Define the state - What information do we need to track?
2. Define the recurrence - How do we compute current state from previous states?
3. Identify base cases - What are the trivial/starting cases?
4. Determine computation order - Bottom-up: smallest to largest
5. Optimize space - Do we need all previous states?

Classic Problems

1. Climbing Stairs

Python

def climb_stairs(n):
    """
    Count ways to climb n stairs (1 or 2 steps at a time).
    Time: O(n), Space: O(1)
    """
    if n <= 2:
        return n

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

    return prev1

# Recurrence: dp[i] = dp[i-1] + dp[i-2]
# Ways to reach step i = ways from (i-1) + ways from (i-2)

JavaScript

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

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

  return prev1;
}

Java

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

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

    return prev1;
}

C++

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

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

    return prev1;
}

2. House Robber

def rob(nums):
    """
    Maximum money from non-adjacent houses.
    Time: O(n), Space: O(1)
    """
    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

# Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# Either skip current house or rob it (can't rob previous)

3. Coin Change

def coin_change(coins, amount):
    """
    Minimum coins needed to make amount.
    Time: O(amount * len(coins)), Space: O(amount)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

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

# Recurrence: dp[a] = min(dp[a - coin] + 1) for all valid coins

4. Longest Increasing Subsequence (LIS)

def length_of_lis(nums):
    """
    Length of longest increasing subsequence.
    Time: O(n²), Space: O(n)
    """
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # dp[i] = LIS ending at i

    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)

# O(n log n) solution using binary search
def length_of_lis_optimal(nums):
    from bisect import bisect_left
    tails = []

    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

5. Longest Common Subsequence (LCS)

def lcs(text1, text2):
    """
    Length of longest common subsequence.
    Time: O(m * n), Space: O(m * n)
    """
    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]

# Recurrence:
# if text1[i] == text2[j]: dp[i][j] = dp[i-1][j-1] + 1
# else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

6. 0/1 Knapsack

def knapsack(weights, values, capacity):
    """
    Maximum value in knapsack of given capacity.
    Time: O(n * capacity), Space: O(capacity)
    """
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Traverse backwards to avoid using same item twice
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

# 2D version for clarity
def knapsack_2d(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):
            # Don't take item i
            dp[i][w] = dp[i - 1][w]
            # Take item i if it fits
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                              dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

7. Edit Distance

def edit_distance(word1, word2):
    """
    Minimum operations to convert word1 to word2.
    Operations: insert, delete, replace
    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # Delete all
    for j in range(n + 1):
        dp[0][j] = j  # Insert all

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # Delete
                    dp[i][j - 1],      # Insert
                    dp[i - 1][j - 1]   # Replace
                )

    return dp[m][n]

8. Unique Paths

def unique_paths(m, n):
    """
    Count paths from top-left to bottom-right.
    Only move right or down.
    Time: O(m * n), Space: O(n)
    """
    dp = [1] * n

    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]

    return dp[n - 1]

def unique_paths_with_obstacles(grid):
    """Handle obstacles"""
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = 1 if grid[0][0] == 0 else 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j - 1]

    return dp[n - 1]

9. Word Break

def word_break(s, word_dict):
    """
    Check if s can be segmented into dictionary words.
    Time: O(n² * m), Space: O(n)
    """
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

10. Maximum Subarray (Kadane’s Algorithm)

def max_subarray(nums):
    """
    Find contiguous subarray with largest sum.
    Time: O(n), Space: O(1)
    """
    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

# Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i])
# Either start new subarray or extend previous

Common DP Patterns

Pattern	Example Problems
1D Linear	Climbing Stairs, House Robber
2D Grid	Unique Paths, Edit Distance
Subsequences	LIS, LCS
Knapsack	0/1 Knapsack, Coin Change
Interval	Matrix Chain, Burst Balloons
String	Word Break, Palindrome Partitioning

Space Optimization

# 2D to 1D: When dp[i][j] only depends on dp[i-1][...]
# Full 2D
dp = [[0] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        dp[i][j] = func(dp[i-1][j], dp[i][j-1])

# Optimized to 1D
dp = [0] * n
for i in range(m):
    for j in range(n):
        dp[j] = func(dp[j], dp[j-1])  # dp[j] is previous row value

# Further optimization: Just track variables
prev, curr = 0, 0

Practice Problems

Easy

Problem	Pattern	Companies
Climbing Stairs	1D Linear	Amazon, Google
House Robber	1D Linear	Amazon, Microsoft
Maximum Subarray	Kadane’s	Amazon, Meta
Best Time to Buy and Sell Stock	1D	Amazon, Meta

Medium

Problem	Pattern	Companies
Coin Change	Unbounded Knapsack	Amazon, Google
Longest Increasing Subsequence	Subsequence	Amazon, Meta
Unique Paths	2D Grid	Amazon, Google
Word Break	String DP	Amazon, Meta
Longest Palindromic Substring	Interval	Amazon, Microsoft
Decode Ways	1D Linear	Amazon, Meta

Hard

Problem	Pattern	Companies
Edit Distance	2D String	Amazon, Google
Longest Valid Parentheses	String DP	Amazon
Regular Expression Matching	2D String	Google, Meta
Burst Balloons	Interval DP	Google
Longest Common Subsequence	2D Subsequence	Amazon, Google

Key Takeaways

1. Identify DP signals - Optimization, counting, feasibility
2. Define state carefully - What information is needed?
3. Write recurrence first - Then implement
4. Start with memoization - Easier to write correctly
5. Optimize after correctness - Convert to tabulation, reduce space

Next Steps

Greedy Algorithms Compare with local optimization strategies

Recursion Review recursive foundations of DP