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.

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)