Dynamic Programming I: 1D and Knapsack

Chapter 27: Dynamic Programming I — 1D and Knapsack

Dynamic programming (DP) is the most frequently tested algorithmic paradigm in interviews, bar none. Its core idea fits in one sentence: break a big problem into overlapping subproblems, solve each subproblem once, and store the result for reuse.

If DP feels hard, it's probably because you're trying to "think up the transition equation" from scratch. The right learning path is: write brute-force recursion → spot repeated computation → add memoization → rewrite as bottom-up iteration. Once you've walked these four steps, DP loses its mystery.

Level 1 · What You Need to Know

27.1 From Brute Force to Dynamic Programming

Classic starter: Climbing Stairs (LeetCode #70)

You're climbing stairs. Each step you can climb 1 or 2 steps. How many distinct ways to reach step n?

Step 1: Brute-force recursion

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

Identical to Fibonacci. Time O(2ⁿ) — at n = 45 it takes seconds.

Step 2: Spot repeated computation

Draw the recursion tree and you'll see climb(3) computed many times:

                climb(5)
               /        \
          climb(4)      climb(3)
          /     \        /    \
     climb(3) climb(2) climb(2) climb(1)
      /   \
  climb(2) climb(1)

Step 3: Add memoization (Top-Down)

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

Cache previously computed results. Time O(n), Space O(n).

Step 4: Bottom-Up

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

Step 5: Space optimization

Since dp[i] only depends on dp[i-1] and dp[i-2], we don't need the full array:

def climb_stairs_optimized(n):
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Time O(n), Space O(1). From O(2ⁿ) to O(n) — that's the power of dynamic programming.

27.2 The Three Core Elements of DP

Every DP problem requires defining three things:

State definition is the hardest part. If you get the state right, the transition equation usually follows naturally.

27.3 Classic 1D DP Problems

House Robber (LeetCode #198)

Houses along a street each contain some money. You can't rob two adjacent houses. Find maximum profit.

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

# Space-optimized
def rob_optimized(nums):
    if not nums:
        return 0
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

Coin Change (LeetCode #322)

Given coin denominations and a total amount, find the minimum number of coins needed.

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

State: dp[i] = minimum coins to make amount i Transition: dp[i] = min(dp[i - coin] + 1) over all coins Base: dp[0] = 0

Longest Increasing Subsequence (LeetCode #300)

def length_of_lis(nums):
    if not nums:
        return 0
    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)

Time O(n²). Can be optimized to O(n log n) with binary search — see Chapter 22.

27.4 When Can DP Be Applied?

DP works when two conditions hold:

1. Optimal substructure: The optimal solution to the problem contains optimal solutions to subproblems. You can construct the overall optimum from subproblem optima.

2. Overlapping subproblems: Different recursive paths recompute the same subproblems. If subproblems don't overlap (each solved only once), it's divide-and-conquer, not DP.

Counterexample: Longest simple path in an unweighted graph. This problem lacks optimal substructure because the longest path may need to "detour," and sub-paths aren't necessarily optimal for their subproblems. This problem is NP-hard.

27.5 Memoization vs. Bottom-Up

Interview strategy: Start with memoization (fast, less error-prone). If the interviewer asks for optimization, convert to bottom-up + space optimization.

Level 2 · How It Works

27.6 0-1 Knapsack

Classic problem: n items, each with weight w[i] and value v[i]. Knapsack capacity W. Each item can be chosen at most once. Maximize total value.

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i-1], values[i-1]
        for j in range(W + 1):
            dp[i][j] = dp[i-1][j]  # don't take item i
            if j >= w:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)  # take item i
    return dp[n][W]

Space optimization to 1D:

The transition only uses the previous row dp[i-1][...]. We can use a single array, but must iterate right to left to avoid using values already overwritten in the current round:

def knapsack_01_optimized(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        w, v = weights[i], values[i]
        for j in range(W, w - 1, -1):  # right to left!
            dp[j] = max(dp[j], dp[j-w] + v)
    return dp[W]

Why right to left? If we go left to right, dp[j-w] may have already been updated in this round (effectively allowing item i to be selected multiple times). Right to left ensures dp[j-w] is still the previous round's value — each item selected at most once.

27.7 Complete Knapsack

Difference from 0-1: each item can be selected unlimited times.

def knapsack_complete(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        w, v = weights[i], values[i]
        for j in range(w, W + 1):  # left to right!
            dp[j] = max(dp[j], dp[j-w] + v)
    return dp[W]

The only difference: inner loop goes left to right. We want to use the current round's updated dp[j-w] (allowing item i to be selected multiple times).

Coin change is a complete knapsack: each coin can be used unlimited times, minimize coins to reach the target amount.

27.8 Multi-Knapsack

Each item can be selected at most c[i] times.

Naive approach: Expand each item into c[i] independent items, then run 0-1 knapsack. Time O(n × W × max(c)).

Binary optimization: Split c[i] items into groups of 1, 2, 4, 8, ..., remainder. For example, c = 13 becomes 1 + 2 + 4 + 6 = 13. Now 13 items become 4 groups processed as 0-1 knapsack. Time O(n × W × log(max(c))).

def knapsack_multi(weights, values, counts, W):
    new_w, new_v = [], []
    for i in range(len(weights)):
        c = counts[i]
        k = 1
        while k <= c:
            new_w.append(weights[i] * k)
            new_v.append(values[i] * k)
            c -= k
            k *= 2
        if c > 0:
            new_w.append(weights[i] * c)
            new_v.append(values[i] * c)
    return knapsack_01_optimized(new_w, new_v, W)

27.9 Knapsack Variants

Counting solutions: Instead of maximum value, count "how many ways to exactly fill the knapsack."

# Target Sum (LeetCode #494)
# Given nums and target, put + or - before each number
# Count ways to achieve target sum
def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (target + total) % 2 != 0 or abs(target) > total:
        return 0
    bag = (target + total) // 2

    dp = [0] * (bag + 1)
    dp[0] = 1  # empty set sums to 0: 1 way
    for num in nums:
        for j in range(bag, num - 1, -1):  # 0-1 knapsack
            dp[j] += dp[j - num]
    return dp[bag]

Exactly fill vs. at most fill:

• At most fill: dp[0] = 0, rest initialized to 0 (maximize value)
• Exactly fill: dp[0] = 0, rest initialized to -inf (only exactly-filled states are valid)

Level 3 · What the Spec Says

27.10 History of Dynamic Programming

The name "Dynamic Programming" was coined by Richard Bellman in 1953 while working at the RAND Corporation. Bellman later explained his choice:

"I chose the name 'dynamic programming' to hide the mathematical nature of my work... The word 'programming' was used in the sense of 'planning' (like military programming), and 'dynamic' was chosen because it sounded impressive and had no precise meaning that could be used against me."

His boss at the time was Secretary of Defense Charles Erwin Wilson, who "had a pathological fear and hatred of the word 'research'." So Bellman used an impressive-sounding but vague name to protect his funding.

Bellman's core contribution is the Bellman equation (Principle of Optimality):

"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision."

Translation: any sub-policy of an optimal policy must itself be optimal. This is the formal statement of "optimal substructure."

27.11 DP vs. Greedy

Greedy (Chapter 26) can be seen as a special case of DP: when the locally optimal choice at each step happens to be globally optimal, you don't need to consider all subproblems — just be greedy.

Example: Coin change with denominations [1, 5, 10, 25] (US coins) — greedy (largest first) is correct. But with [1, 3, 4], making 6: greedy picks 4+1+1 = 3 coins, DP picks 3+3 = 2 coins. Greedy fails.

27.12 Formal Definition of Optimal Substructure

Let S* be the optimal solution to problem P. If S* decomposes into solutions S₁*, S₂*, ..., Sₖ* for subproblems P₁, P₂, ..., Pₖ, and each Sᵢ* is optimal for Pᵢ, then P has optimal substructure.

Proof technique (Cut-and-Paste): Proof by contradiction. Assume some subproblem solution Sᵢ* is not optimal — then a better Sᵢ' exists. Replacing Sᵢ* with Sᵢ' would improve the overall solution, contradicting S*'s optimality.

This proof method comes from CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms, Chapter 15.

27.13 State Count and Computational Cost

DP time complexity = number of states × transition cost per state.

Note that 0-1 knapsack's O(nW) is pseudo-polynomial: W is a numeric value, not input length. If W is represented in b bits, then W = 2^b, and time O(n × 2^b) is exponential. This is why the knapsack problem is NP-hard (see Chapter 37 on complexity theory).

Level 4 · Edge Cases and Pitfalls

27.14 Common State Definition Errors

Error 1: Not enough state dimensions

# Best Time to Buy and Sell Stock (LeetCode #121) — wrong state
# dp[i] = max profit on day i?
# Problem: don't know whether we're holding stock

# Correct: dp[i][0] = max profit on day i, not holding
#          dp[i][1] = max profit on day i, holding
def max_profit(prices):
    n = len(prices)
    if n < 2:
        return 0
    dp = [[0, 0] for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])  # sell
        dp[i][1] = max(dp[i-1][1], -prices[i])                # buy (only once)
    return dp[n-1][0]

Error 2: Wrong iteration direction

0-1 knapsack inner loop goes right to left; complete knapsack goes left to right. Swap them and you solve a different problem.

Error 3: Missing base cases

# Decode Ways (LeetCode #91)
# "12" can be decoded as "AB" or "L"
def num_decodings(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # empty string has 1 decoding (easy to forget!)
    dp[1] = 1
    for i in range(2, n + 1):
        one = int(s[i-1])
        two = int(s[i-2:i])
        if 1 <= one <= 9:
            dp[i] += dp[i-1]
        if 10 <= two <= 26:
            dp[i] += dp[i-2]
    return dp[n]

27.15 Space Optimization Techniques

Rolling variables: When dp[i] depends only on dp[i-1] and dp[i-2], use two variables instead of an array.

# General template
prev2, prev1 = initial_0, initial_1
for i in range(2, n + 1):
    curr = f(prev1, prev2)
    prev2, prev1 = prev1, curr

2D to 1D: When dp[i][j] depends only on dp[i-1][...], drop the first dimension. Watch iteration direction.

27.16 Interview Problems

Problem 1: Minimum Path Sum (LeetCode #64)

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(m):
        dp[0] = dp[0] + grid[i][0]
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
    return dp[n-1]

Problem 2: Word Break (LeetCode #139)

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

Problem 3: Partition Equal Subset Sum (LeetCode #416)

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):  # 0-1 knapsack: right to left
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

This perfectly demonstrates problem transformation: convert "can we split into two equal-sum subsets" into "can we select numbers summing to exactly total/2" — a 0-1 knapsack exact-fill problem.

27.17 Universal DP Problem-Solving Framework

When facing a new DP problem, think through these steps:

1. Define state: What does dp[i] or dp[i][j] represent? Usually "ending at i" or "considering first i elements"
2. Find transition: How is dp[i] derived from earlier states? What choices exist (take/skip, come from where)?
3. Set base cases: What are the answers for the smallest subproblems?
4. Determine iteration order: Ensure all dependencies are computed before dp[i]
5. Determine return value: dp[n], max(dp), or dp[n][m]?
6. Optimize space (optional): Can we reduce dimensions?

In interviews, manually trace a small example to verify the transition equation's correctness — far more reliable than staring at code.

Chapter Summary

Exercises:

1. Coin Change II (LeetCode #518): Given coin denominations and total amount, count distinct combinations. (Hint: complete knapsack + counting)
2. Integer Break (LeetCode #343): Split positive integer n into at least two positive integers. Maximize their product.
3. Longest Palindromic Substring (LeetCode #5): Solve with DP and compare to Manacher's algorithm.
4. Modify the 0-1 knapsack to output which items were selected (not just the maximum value).

Next chapter: Chapter 28 enters two-dimensional DP — edit distance, longest common subsequence, and interval DP. State definitions expand from 1D to 2D, transitions are more complex, but the core idea is exactly the same.