35  Algorithm Design, Dynamic Programming I

36 Algorithm Design: Dynamic Programming I

Week 7, Session 1. CSS 343.

36.1 Warmup

Climbing Stairs (#70). The Fibonacci-shaped recurrence. We solved it iteratively in 342 chapter 9. Now we name the paradigm.

class Solution {
 public:
  int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
      dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
  }
};

That is bottom-up DP. The hallmark: a recurrence relating dp[i] to earlier dp values.

36.2 Learning objectives

  1. Identify the two structural properties that make DP applicable.
  2. Convert a recursive exponential solution to a memoized O(n) solution.
  3. Define subproblem notation, write a recurrence, fill a DP table for 0-1 Knapsack.
  4. Solve Coin Change using tabulation; contrast with greedy failure.
  5. Solve House Robber by recognizing its recurrence.

36.3 The two properties

DP applies when a problem has:

  1. Overlapping subproblems: the same subproblem is solved multiple times.
  2. Optimal substructure: optimal solutions are built from optimal subsolutions.

Fibonacci has both. Knapsack has both. Sorting does not (no overlap, each subarray is unique).

36.4 Memoization vs. tabulation

Two ways to do DP:

  • Memoization (top-down): write the recursive solution, add a cache.
  • Tabulation (bottom-up): explicitly fill a table from base cases up.

Top-down for Fibonacci:

unordered_map<int, int> memo;
int fib(int n) {
  if (n <= 1) return n;
  if (memo.count(n) == 1) return memo[n];
  return memo[n] = fib(n-1) + fib(n-2);
}

Bottom-up for Fibonacci:

int fib(int n) {
  if (n <= 1) return n;
  int a = 0, b = 1;
  for (int i = 2; i <= n; ++i) {
    int c = a + b;
    a = b;
    b = c;
  }
  return b;
}

Both are O(n). Tabulation is usually faster (no recursion overhead, better cache) and easier to space-optimize. Memoization is easier to write directly from the recurrence.

36.5 0/1 Knapsack: the canonical DP

Items have value v[i] and weight w[i]. Capacity W. Choose a subset maximizing value within capacity.

Subproblem: dp[i][c] = max value using items 0..i-1 with capacity c.

Recurrence:

\[ dp[i][c] = \begin{cases} dp[i-1][c] & \text{if } w[i-1] > c \\ \max(dp[i-1][c], \; v[i-1] + dp[i-1][c - w[i-1]]) & \text{otherwise} \end{cases} \]

In code:

int knapsack(vector<int>& v, vector<int>& w, int W) {
  int n = v.size();
  vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
  for (int i = 1; i <= n; ++i) {
    for (int c = 0; c <= W; ++c) {
      dp[i][c] = dp[i-1][c];
      if (w[i-1] <= c) {
        dp[i][c] = max(dp[i][c], v[i-1] + dp[i-1][c - w[i-1]]);
      }
    }
  }
  return dp[n][W];
}

O(nW) time and space. (Sometimes called pseudo-polynomial because it depends on W, not log W.)

36.5.1 Space optimization

dp[i] only depends on dp[i-1]. So one row suffices. Iterate c in reverse so the previous row’s values are not yet overwritten when needed:

int knapsack1d(vector<int>& v, vector<int>& w, int W) {
  vector<int> dp(W + 1, 0);
  int n = v.size();
  for (int i = 0; i < n; ++i) {
    for (int c = W; c >= w[i]; --c) {
      dp[c] = max(dp[c], v[i] + dp[c - w[i]]);
    }
  }
  return dp[W];
}

Same answer, O(W) space.

36.6 Coin Change: fixing greedy’s failure

int coinChange(vector<int>& coins, int amount) {
  vector<int> dp(amount + 1, amount + 1);  // sentinel
  dp[0] = 0;
  for (int a = 1; a <= amount; ++a) {
    for (int c : coins) {
      if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

Subproblem: dp[a] = minimum coins to make amount a. Recurrence: for each coin c, dp[a] ≤ dp[a-c] + 1.

For coins {1, 3, 4}, amount 6: dp = [0, 1, 2, 1, 1, 2, 2]. Answer: 2 (two 3s). Greedy would have said 3.

36.7 House Robber

House Robber (#198). Cannot rob two adjacent houses. Maximize loot.

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

int rob(vector<int>& nums) {
  int prev = 0, curr = 0;
  for (int n : nums) {
    int next = max(curr, prev + n);
    prev = curr;
    curr = next;
  }
  return curr;
}

Space-optimized to O(1): we only need the previous two values.

36.8 The DP design checklist

When facing a new problem and you suspect DP:

  1. Define the subproblem in words. “dp[i] = the maximum sum of a non-adjacent subset of nums[0..i].”
  2. Write the recurrence. Include base cases.
  3. Decide top-down or bottom-up.
  4. Code it.
  5. Space-optimize if possible.

The hardest step is (1). Most DP failures trace to a poorly defined subproblem.

DP feels mystical at first. It is not. It is just memoized recursion with a table. The mysticism comes from defining the subproblem, and that comes only with practice. A good programmer is one who can recognize patterns. DP is a pattern. Once you have hand-traced your first knapsack table on paper, you are done with the mysticism.

36.9 Try it

Solve Min Cost Climbing Stairs (#746). You can start at index 0 or 1; from index i you pay cost[i] to step. Reach beyond the array. Minimum total cost?

int minCostClimbingStairs(vector<int>& cost) {
  int n = cost.size();
  vector<int> dp(n + 1, 0);
  for (int i = 2; i <= n; ++i) {
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
  }
  return dp[n];
}

36.10 Self-check

1. The two properties required for DP are:
b. Without overlap, memoization saves nothing. Without optimal substructure, the recurrence is wrong.
2. 0/1 knapsack with the 1D DP trick iterates capacity in reverse because:
d. Reverse iteration ensures dp[c - w[i]] still refers to the previous row.

36.11 Challenges

  1. Coin Change (#322).
  2. House Robber (#198) and House Robber II (#213).
  3. Partition Equal Subset Sum (#416): 0/1 knapsack variant.
  4. Implement 0/1 knapsack both 2D and 1D. Confirm same answers on test inputs.

36.12 Where this fits

Single-variable DP. Next chapter expands to two-dimensional DPs on strings and grids.

You are here Coming up
DP framework, memoization, tabulation, knapsack Chapter 34: DP on strings (LCS, edit distance, LIS)