Dynamic Programming — Bottom-Up Technique

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into simpler overlapping subproblems, solving each subproblem only once, and storing the result for future use. It transforms exponential brute-force solutions into polynomial-time algorithms.

Two conditions must both hold for DP to apply:

1. Optimal Substructure

The optimal solution to the full problem can be constructed from optimal solutions of its subproblems.

Example: Shortest path from A to D through B and C

    A ---3--- B ---2--- C ---4--- D

Shortest(A, D) = Shortest(A, B) + Shortest(B, C) + Shortest(C, D)

The overall optimal path is built from optimal sub-paths.

2. Overlapping Subproblems

The same subproblems appear multiple times during recursion. Without DP, we wastefully recompute them.

Fibonacci call tree for fib(5):

                    fib(5)
                   /      \
              fib(4)       fib(3)        ← fib(3) computed TWICE
             /     \       /     \
         fib(3)  fib(2)  fib(2)  fib(1)  ← fib(2) computed THREE times
        /    \
    fib(2) fib(1)

Total calls without DP: 15  (exponential growth)
Total calls with DP:     6  (linear)

Key insight: If a problem has optimal substructure but no overlapping subproblems, use Divide and Conquer (e.g., merge sort) instead of DP. If subproblems overlap, DP saves exponential work by caching results.

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

Top-Down (Memoization)

Start with the original problem, recurse into subproblems
Cache (memoize) results in a hash map or array
Natural — follows the recursive thinking pattern
Lazy: only computes subproblems actually needed
Downside: recursion overhead, potential stack overflow for deep recursion

CPP

// Top-Down Fibonacci
int memo[1001];

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];       // already computed?
    return memo[n] = fib(n-1) + fib(n-2);    // cache & return
}

int main() {
    memset(memo, -1, sizeof(memo));
    // ... use fib() ...
}

Bottom-Up (Tabulation) — FOCUS OF THIS GUIDE

Start with the smallest subproblems, build up to the answer
Fill a DP table iteratively in a carefully chosen order
Eager: computes all subproblems in order
Usually faster (no recursion overhead, better cache locality)
Must determine the correct fill order for the table

CPP

// Bottom-Up Fibonacci
int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

Side-by-Side Comparison

When to Use Which?

Aspect	Top-Down	Bottom-Up
Thinking style	Recursive, natural	Iterative, requires planning
States computed	Only needed ones	All states
Speed	Slower (recursion)	Faster (iteration)
Stack overflow	Possible for large n	Not an issue
Space optimize	Harder	Easier (rolling arrays)
Implementation	Often simpler	Requires fill order

Rule of thumb: Think top-down first (easier to derive the recurrence), then convert to bottom-up for production code (faster, space-optimizable).

The Bottom-Up Framework (5 Steps)

Every bottom-up DP solution follows this framework:

The hardest step is Step 1 — choosing the right state definition. A bad state definition leads to incorrect or inefficient transitions. We will see many examples to build intuition.

Pattern 1: 1D DP

The simplest DP problems use a 1D array where dp[i] represents the answer for a prefix or suffix of the input.

Example: Climbing Stairs (LC 70)

Problem: You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of an n-step staircase?

Framework application:

Step 1 — State:      dp[i] = number of distinct ways to reach step i
Step 2 — Base:       dp[0] = 1 (one way to stay at ground: do nothing)
                     dp[1] = 1 (one way to reach step 1: single step)
Step 3 — Transition: dp[i] = dp[i-1] + dp[i-2]
                     (arrive from step i-1 with 1 step, or from i-2 with 2 steps)
Step 4 — Order:      left to right, i = 2, 3, ..., n
Step 5 — Answer:     dp[n]

Visual walkthrough for n = 5:

Step:     0    1    2    3    4    5
dp:     [ 1    1    2    3    5    8 ]
                ↑    ↑    ↑    ↑    ↑
              base  1+1  1+2  2+3  3+5

Ways to reach step 5:
  Step 4 → Step 5 (take 1 step): 5 ways
  Step 3 → Step 5 (take 2 steps): 3 ways
  Total: 5 + 3 = 8 ways

CPP

int climbStairs(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;  // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Space optimization: Since dp[i] depends only on dp[i-1] and dp[i-2], we need only two variables instead of an entire array. This reduces space from O(n) to O(1).

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

Example: House Robber (LC 198)

Problem: Given an array nums where nums[i] is the money at house i, find the maximum money you can rob without robbing two adjacent houses.

Intuition: At each house, you have two choices:

Skip this house — your best is whatever you had from the previous house
Rob this house — add its value to the best from two houses back (can't rob adjacent)

Decision tree without DP (exponential):

nums = [2, 7, 9, 3, 1]

                          house 0
                        /         \
                   rob(2)        skip
                   /    \          |
              skip     rob(9)    rob(7)
               |       /   \     /   \
            rob(9)  skip  rob(1) skip  rob(3)
            ...     ...          ...   ...

Many paths recompute the same subproblems!

Framework application:

Step 1 — State:      dp[i] = max money robbing from houses 0..i
Step 2 — Base:       dp[0] = nums[0]
                     dp[1] = max(nums[0], nums[1])
Step 3 — Transition: dp[i] = max(dp[i-1],           ← skip house i
                                  dp[i-2] + nums[i]) ← rob house i
Step 4 — Order:      left to right, i = 2, 3, ..., n-1
Step 5 — Answer:     dp[n-1]

Visual walkthrough for nums = [2, 7, 9, 3, 1]:

i=0: dp[0] = 2                        Rob house 0
i=1: dp[1] = max(2, 7) = 7            Rob house 1 (better than house 0 alone)
i=2: dp[2] = max(7, 2+9) = 11         Rob houses 0,2 → 2+9=11 > 7
i=3: dp[3] = max(11, 7+3) = 11        Skip house 3 → 11 > 10
i=4: dp[4] = max(11, 11+1) = 12       Rob houses 0,2,4 → 2+9+1=12

dp:  [ 2    7    11   11   12 ]
Answer: 12

CPP

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    // Space-optimized: only need two previous values
    int prev2 = nums[0];                    // dp[i-2]
    int prev1 = max(nums[0], nums[1]);      // dp[i-1]

    for (int i = 2; i < n; i++) {
        int curr = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

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

Example: Longest Increasing Subsequence (LC 300)

Problem: Given an integer array nums, find the length of the longest strictly increasing subsequence.

Key insight: The state must capture where the subsequence ends, because future elements can only extend a subsequence if they are greater than its last element.

Framework application:

Step 1 — State:      dp[i] = length of LIS ending at index i
                     (the subsequence MUST include nums[i] as its last element)
Step 2 — Base:       dp[i] = 1 for all i (each element alone is a subsequence)
Step 3 — Transition: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
                     (extend any valid shorter subsequence ending before i)
Step 4 — Order:      left to right, i = 0, 1, ..., n-1
Step 5 — Answer:     max(dp[i]) for all i (LIS could end anywhere)

Visual walkthrough for nums = [10, 9, 2, 5, 3, 7, 101, 18]:

i=0: nums[0]=10   dp=[1]                     LIS: [10]
     No j < 0, so dp[0] = 1

i=1: nums[1]=9    dp=[1,1]                   LIS: [9]
     j=0: nums[0]=10 > 9, skip

i=2: nums[2]=2    dp=[1,1,1]                 LIS: [2]
     j=0: 10 > 2, skip
     j=1: 9 > 2, skip

i=3: nums[3]=5    dp=[1,1,1,2]               LIS: [2,5]
     j=0: 10 > 5, skip
     j=1: 9 > 5, skip
     j=2: 2 < 5, dp[3] = max(1, dp[2]+1) = 2  ✓

i=4: nums[4]=3    dp=[1,1,1,2,2]             LIS: [2,3]
     j=2: 2 < 3, dp[4] = max(1, 1+1) = 2    ✓

i=5: nums[5]=7    dp=[1,1,1,2,2,3]           LIS: [2,3,7]
     j=2: 2 < 7, dp[5] = max(1, 1+1) = 2
     j=3: 5 < 7, dp[5] = max(2, 2+1) = 3    ✓
     j=4: 3 < 7, dp[5] = max(3, 2+1) = 3

i=6: nums[6]=101  dp=[1,1,1,2,2,3,4]         LIS: [2,3,7,101]
     j=5: 7 < 101, dp[6] = max(.., 3+1) = 4 ✓

i=7: nums[7]=18   dp=[1,1,1,2,2,3,4,4]       LIS: [2,3,7,18]
     j=5: 7 < 18, dp[7] = max(.., 3+1) = 4  ✓

Answer: max(dp) = 4

CPP

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

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

O(n log n) Solution: Patience Sorting

Maintain an array tails where tails[i] is the smallest possible tail element for an increasing subsequence of length i+1.

Intuition: For each new element, either extend the longest subsequence (append) or replace an element in tails to keep tails as small as possible (enabling future extensions).

nums = [10, 9, 2, 5, 3, 7, 101, 18]

Process 10:   tails = [10]           (start new pile)
Process 9:    tails = [9]            (replace 10, 9 is smaller tail for length 1)
Process 2:    tails = [2]            (replace 9)
Process 5:    tails = [2, 5]         (extend: 5 > 2)
Process 3:    tails = [2, 3]         (replace 5: better tail for length 2)
Process 7:    tails = [2, 3, 7]      (extend: 7 > 3)
Process 101:  tails = [2, 3, 7, 101] (extend)
Process 18:   tails = [2, 3, 7, 18]  (replace 101)

Answer: tails.size() = 4

For each element, use binary search on tails to find the position → O(log n) per element.

CPP

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);
        else
            *it = x;
    }
    return tails.size();
}

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

Example: Maximum Subarray / Kadane's Algorithm (LC 53)

Problem: Find the contiguous subarray with the largest sum.

Intuition: At each index, decide: extend the current subarray, or start a new one here.

Step 1 — State:      dp[i] = max subarray sum ending at index i
Step 2 — Base:       dp[0] = nums[0]
Step 3 — Transition: dp[i] = max(nums[i], dp[i-1] + nums[i])
                     (start fresh at i, or extend from i-1)
Step 4 — Order:      left to right
Step 5 — Answer:     max(dp[i]) for all i

Visual for nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

i:      0    1    2    3    4    5    6    7    8
nums:  -2    1   -3    4   -1    2    1   -5    4
dp:    -2    1   -2    4    3    5    6    1    5
              ↑         ↑                   ↑
           start      start              extend
           fresh      fresh              from 6

Best subarray: [4, -1, 2, 1] with sum 6

CPP

int maxSubArray(vector<int>& nums) {
    int curr = nums[0], best = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        curr = max(nums[i], curr + nums[i]);
        best = max(best, curr);
    }
    return best;
}

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

Example: Coin Change (LC 322)

Problem: Given coins of different denominations and a total amount, find the minimum number of coins needed. Return -1 if impossible.

Intuition: For each amount, try every coin. The best solution for amount a is 1 + the best solution for amount a - coin.

Step 1 — State:      dp[a] = min coins to make amount a
Step 2 — Base:       dp[0] = 0 (zero coins for zero amount)
Step 3 — Transition: dp[a] = min(dp[a - c] + 1) for each coin c where c <= a
Step 4 — Order:      a = 1, 2, ..., amount
Step 5 — Answer:     dp[amount] (or -1 if dp[amount] is still infinity)

Visual for coins = [1, 3, 4], amount = 6:

a=0: dp[0] = 0                          (base case)
a=1: coin 1: dp[1-1]+1 = 1              dp[1] = 1    → [1]
a=2: coin 1: dp[2-1]+1 = 2              dp[2] = 2    → [1,1]
a=3: coin 1: dp[2]+1 = 3
     coin 3: dp[0]+1 = 1                dp[3] = 1    → [3]
a=4: coin 1: dp[3]+1 = 2
     coin 3: dp[1]+1 = 2
     coin 4: dp[0]+1 = 1                dp[4] = 1    → [4]
a=5: coin 1: dp[4]+1 = 2
     coin 3: dp[2]+1 = 3
     coin 4: dp[1]+1 = 2                dp[5] = 2    → [1,4]
a=6: coin 1: dp[5]+1 = 3
     coin 3: dp[3]+1 = 2
     coin 4: dp[2]+1 = 3                dp[6] = 2    → [3,3]

dp:  [ 0  1  2  1  1  2  2 ]
Answer: dp[6] = 2  (use coins 3 + 3)

Why greedy fails here: Greedy would pick coin 4 first → 4 + 1 + 1 = 3 coins. DP finds 3 + 3 = 2 coins.

CPP

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);  // amount+1 acts as "infinity"
    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];
}

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

Example: Word Break (LC 139)

Problem: Given a string s and a dictionary wordDict, determine if s can be segmented into a space-separated sequence of dictionary words.

Intuition: dp[i] is true if the first i characters of s can be segmented. For each position i, check every possible last word.

Step 1 — State:      dp[i] = true if s[0..i-1] can be broken into dictionary words
Step 2 — Base:       dp[0] = true (empty string is trivially segmentable)
Step 3 — Transition: dp[i] = true if there exists j < i such that
                              dp[j] == true AND s[j..i-1] is in the dictionary
Step 4 — Order:      i = 1, 2, ..., n
Step 5 — Answer:     dp[n]

Visual for s = "leetcode", dict = {"leet", "code"}:

s:     l  e  e  t  c  o  d  e
idx:   0  1  2  3  4  5  6  7

dp[0] = true  (base: empty prefix)
dp[1] = false (no word ends here)
dp[2] = false
dp[3] = false
dp[4] = true  ← dp[0]=true AND s[0..3]="leet" in dict!
dp[5] = false
dp[6] = false
dp[7] = false
dp[8] = true  ← dp[4]=true AND s[4..7]="code" in dict!

Answer: dp[8] = true → "leet" + "code"

CPP

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;  // found one valid split, no need to check more
            }
        }
    }
    return dp[n];
}

Time: O(n^2 * k) where k is average word length (for substr + hash) | Space: O(n)

Optimization: Instead of checking all j < i, iterate over words in the dictionary and check if s ends with that word at position i. This is better when the dictionary is small.

Example: Decode Ways (LC 91)

Problem: A message encoded as digits '1' to '26' maps to 'A' to 'Z'. Given a digit string, count the number of ways to decode it.

Step 1 — State:      dp[i] = number of ways to decode s[0..i-1]
Step 2 — Base:       dp[0] = 1 (empty string: one way to decode nothing)
                     dp[1] = (s[0] != '0') ? 1 : 0
Step 3 — Transition: if s[i-1] != '0': dp[i] += dp[i-1]   (single digit)
                     if s[i-2..i-1] in [10,26]: dp[i] += dp[i-2]  (two digits)
Step 4 — Order:      left to right
Step 5 — Answer:     dp[n]

Visual for s = "226":

s:     2    2    6

dp[0] = 1           (base)
dp[1] = 1           ("2" → B)
dp[2] = dp[1] + dp[0] = 2
        ↑ s[1]='2' valid single  → dp[1]=1
        ↑ s[0..1]="22" ∈ [10,26] → dp[0]=1
dp[3] = dp[2] + dp[1] = 3
        ↑ s[2]='6' valid single  → dp[2]=2
        ↑ s[1..2]="26" ∈ [10,26] → dp[1]=1

Answer: 3 → {"BZ", "VF", "BBF"} wait let's verify:
  "2|2|6" → B,B,F
  "22|6"  → V,F
  "2|26"  → B,Z
  ✓ Three decodings

CPP

int numDecodings(string s) {
    int n = s.size();
    if (n == 0 || s[0] == '0') return 0;

    int prev2 = 1;  // dp[0]
    int prev1 = 1;  // dp[1]

    for (int i = 2; i <= n; i++) {
        int curr = 0;
        // Single digit decode
        if (s[i-1] != '0')
            curr += prev1;
        // Two digit decode
        int twoDigit = (s[i-2] - '0') * 10 + (s[i-1] - '0');
        if (twoDigit >= 10 && twoDigit <= 26)
            curr += prev2;

        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

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

Pattern 2: 2D DP

When a single dimension isn't enough to capture the state, we add a second dimension. Common patterns: two indices into a string/array, or index + capacity/budget.

Example: Unique Paths (LC 62)

Problem: A robot at top-left of an m x n grid can only move right or down. How many unique paths to the bottom-right?

Step 1 — State:      dp[i][j] = number of paths from (0,0) to (i,j)
Step 2 — Base:       dp[0][j] = 1 for all j (only way: go right)
                     dp[i][0] = 1 for all i (only way: go down)
Step 3 — Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]
                     (arrive from above or from left)
Step 4 — Order:      row by row, left to right
Step 5 — Answer:     dp[m-1][n-1]

Visual for m=3, n=4:

    col 0  col 1  col 2  col 3

r0    1      1      1      1     ← only way is right
r1    1      2      3      4
r2    1      3      6     10     ← answer
  ↑
  only way is down

dp[2][3] = 10

How dp[2][2] = 6:
  from above: dp[1][2] = 3
  from left:  dp[2][1] = 3
  total: 3 + 3 = 6

CPP

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);  // Space-optimized: single row
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j-1];
            // dp[j] already has the value from row above (dp[i-1][j])
            // dp[j-1] has the current row's left value (dp[i][j-1])
        }
    }
    return dp[n-1];
}

Time: O(m * n) | Space: O(n) with rolling array optimization

Example: 0/1 Knapsack

Problem: Given n items with weights and values, and a knapsack of capacity W, find the maximum total value without exceeding the weight limit. Each item can be used at most once.

This is THE canonical DP problem. Master this, and many other problems become variations.

Step 1 — State:      dp[i][w] = max value using items 0..i-1 with capacity w
Step 2 — Base:       dp[0][w] = 0 for all w (no items → no value)
Step 3 — Transition:
    If weight[i-1] > w:                     (item too heavy)
        dp[i][w] = dp[i-1][w]
    Else:
        dp[i][w] = max(dp[i-1][w],                        ← skip item i
                       dp[i-1][w - weight[i-1]] + value[i-1])  ← take item i
Step 4 — Order:      row by row (i = 1..n), within each row: w = 0..W
Step 5 — Answer:     dp[n][W]

Visual for weights = [1, 3, 4, 5], values = [1, 4, 5, 7], W = 7:

             w=0   w=1   w=2   w=3   w=4   w=5   w=6   w=7

i=0 (none)    0     0     0     0     0     0     0     0
i=1 (1,1)     0     1     1     1     1     1     1     1
i=2 (3,4)     0     1     1     4     5     5     5     5
i=3 (4,5)     0     1     1     4     5     6     6     9
i=4 (5,7)     0     1     1     4     5     7     8     9
                                                         ↑
                                                      answer

Tracing back dp[4][7] = 9:
  dp[4][7] = max(dp[3][7], dp[3][2] + 7) = max(9, 1+7) = 9 → skip item 4
  dp[3][7] = max(dp[2][7], dp[2][3] + 5) = max(5, 4+5) = 9 → take item 3 (w=4, v=5)
  dp[2][3] = max(dp[1][3], dp[1][0] + 4) = max(1, 0+4) = 4 → take item 2 (w=3, v=4)
  dp[1][0] = 0 → no more items fit
  Selected: items 2 and 3 → weight = 3+4 = 7, value = 4+5 = 9 ✓

2D solution:

CPP

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];  // skip
            if (weight[i-1] <= w) {
                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
            }
        }
    }
    return dp[n][W];
}

1D space optimization — iterate w backwards to avoid using updated values:

Why backwards? When computing dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt] + val), the 1D array dp[w] stores "previous row" values. We need dp[w-wt] to still hold the row i-1 value, not an already-updated row i value.

CPP

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weight[i]; w--) {  // BACKWARDS!
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

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

Note on Unbounded Knapsack (each item can be used unlimited times): iterate w forwards instead, since reusing the updated value means we can pick the same item again.

Example: Edit Distance (LC 72)

Problem: Given two strings word1 and word2, find the minimum number of operations (insert, delete, replace) to convert word1 into word2.

Intuition: Compare characters from the end. If they match, no operation needed. If not, try all three operations and take the minimum.

Step 1 — State:      dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]
Step 2 — Base:       dp[0][j] = j (insert j characters)
                     dp[i][0] = i (delete i characters)
Step 3 — Transition:
    If word1[i-1] == word2[j-1]:
        dp[i][j] = dp[i-1][j-1]          (characters match, no operation)
    Else:
        dp[i][j] = 1 + min(
            dp[i-1][j],       ← DELETE word1[i-1]  (word1 shrinks)
            dp[i][j-1],       ← INSERT word2[j-1]  (word2 shrinks effectively)
            dp[i-1][j-1]      ← REPLACE word1[i-1] with word2[j-1]
        )
Step 4 — Order:      row by row, left to right
Step 5 — Answer:     dp[m][n] where m=|word1|, n=|word2|

Visual for "horse" → "ros":

          ""    r    o    s

  ""       0    1    2    3
  h        1    1    2    3
  o        2    2    1    2
  r        3    2    2    2
  s        4    3    3    2
  e        5    4    4    3
                          ↑
                       answer = 3

Trace the operations (path from dp[5][3] back to dp[0][0]):
  dp[5][3] = 3: 'e' ≠ 's' → replace 'e' with 's'? No, let's trace:
    Actually: dp[5][3] = 1 + min(dp[4][3], dp[5][2], dp[4][2])
            = 1 + min(2, 4, 3) = 1 + 2 = 3 → DELETE 'e'
  dp[4][3] = 2: 's' == 's' → match, go diagonal to dp[3][2]
  dp[3][2] = 2: 'r' ≠ 'o' → 1 + min(dp[2][2], dp[3][1], dp[2][1])
            = 1 + min(1, 2, 2) = 2 → REPLACE 'r' with 'o'
  dp[2][2] = 1: 'o' == 'o' → match, go to dp[1][1]
  dp[1][1] = 1: 'h' ≠ 'r' → 1 + min(dp[0][1], dp[1][0], dp[0][0])
            = 1 + min(1, 1, 0) = 1 → REPLACE 'h' with 'r'
  dp[0][0] = 0: done!

Operations: replace 'h'→'r', replace 'r'→'o', delete 'e'
  horse → rorse → roose → ... Actually:
  horse → rorse (replace h→r)
  rorse → rose  (remove second r)
  rose  → ros   (remove e)
  3 operations ✓

CPP

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // Base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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];
}

Time: O(m * n) | Space: O(m * n), optimizable to O(min(m, n)) with rolling array

Example: Longest Common Subsequence (LC 1143)

Problem: Find the length of the longest common subsequence of two strings.

Key difference from substring: Elements don't need to be contiguous, but must maintain relative order.

Step 1 — State:      dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1]
Step 2 — Base:       dp[0][j] = 0, dp[i][0] = 0 (empty string → LCS is 0)
Step 3 — Transition:
    If text1[i-1] == text2[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1    (both characters in LCS)
    Else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])  (skip one or the other)
Step 4 — Order:      row by row, left to right
Step 5 — Answer:     dp[m][n]

Visual for text1 = "abcde", text2 = "ace":

          ""    a    c    e

  ""       0    0    0    0
  a        0    1    1    1     ← 'a' matches 'a'
  b        0    1    1    1
  c        0    1    2    2     ← 'c' matches 'c'
  d        0    1    2    2
  e        0    1    2    3     ← 'e' matches 'e'
                          ↑
                       answer = 3, LCS = "ace"

CPP

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int 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] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

Time: O(m * n) | Space: O(m * n), optimizable to O(min(m, n))

Example: Minimum Path Sum (LC 64)

Problem: Given a grid filled with non-negative numbers, find a path from top-left to bottom-right that minimizes the sum. Can only move right or down.

Step 1 — State:      dp[i][j] = min path sum from (0,0) to (i,j)
Step 2 — Base:       dp[0][0] = grid[0][0]
                     dp[0][j] = dp[0][j-1] + grid[0][j]  (first row: only right)
                     dp[i][0] = dp[i-1][0] + grid[i][0]  (first col: only down)
Step 3 — Transition: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Step 4 — Order:      row by row, left to right
Step 5 — Answer:     dp[m-1][n-1]

Visual for grid = [[1,3,1],[1,5,1],[4,2,1]]:

Grid:            DP table:
 1  3  1          1   4   5
 1  5  1          2   7   6
 4  2  1          6   8   7  ← answer = 7

Path: 1 → 3 → 1 → 1 → 1 = 7
  or: 1 → 1 → 5 → 1 → 1 = 9 (worse)
  or: 1 → 1 → 4 → 2 → 1 = 9 (worse)

The min path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2) = 1+3+1+1+1 = 7

CPP

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    // Modify grid in-place to save space
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            else if (i == 0) grid[i][j] += grid[i][j-1];
            else if (j == 0) grid[i][j] += grid[i-1][j];
            else grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[m-1][n-1];
}

Time: O(m * n) | Space: O(1) if we modify the input

Pattern 3: Interval DP

Interval DP solves problems where we process a contiguous range [i, j] by splitting it at every possible point and combining results. The table is filled by increasing interval length.

Example: Matrix Chain Multiplication

Problem: Given matrices A1 (p0 x p1), A2 (p1 x p2), ..., An (pn-1 x pn), find the parenthesization that minimizes the total scalar multiplications.

Why order matters: Multiplying A(10x30) * B(30x5) * C(5x60):

(AB)C: 10305 + 10560 = 1500 + 3000 = 4500
A(BC): 30560 + 103060 = 9000 + 18000 = 27000

Same result, 6x difference in cost!

Step 1 — State:   dp[i][j] = min cost to multiply matrices i through j
Step 2 — Base:    dp[i][i] = 0 (single matrix, no multiplication)
Step 3 — Transition:
    dp[i][j] = min over k in [i, j-1] of:
        dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]
        (cost of left part + cost of right part + cost to combine)
Step 4 — Order:   by increasing chain length (len = 2, 3, ..., n)
Step 5 — Answer:  dp[1][n]

Visual for dims = [10, 30, 5, 60] (3 matrices):

Chain length 1 (base):
  dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0

Chain length 2:
  dp[1][2]: k=1 → dp[1][1] + dp[2][2] + 10*30*5 = 1500
  dp[2][3]: k=2 → dp[2][2] + dp[3][3] + 30*5*60 = 9000

Chain length 3:
  dp[1][3]:
    k=1 → dp[1][1] + dp[2][3] + 10*30*60 = 0 + 9000 + 18000 = 27000
    k=2 → dp[1][2] + dp[3][3] + 10*5*60  = 1500 + 0 + 3000  = 4500 ← min!

Answer: dp[1][3] = 4500

CPP

int matrixChainOrder(vector<int>& dims) {
    int n = dims.size() - 1;  // number of matrices
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // len = chain length
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[1][n];
}

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

Example: Burst Balloons (LC 312)

Problem: Given n balloons with numbers, burst them to maximize coins. When you burst balloon i, you get nums[left] * nums[i] * nums[right] coins.

Key insight: Instead of thinking "which balloon to burst first", think "which balloon to burst last" in each interval. This gives clean subproblems because the last balloon to burst acts as a divider.

Step 1 — State:   dp[i][j] = max coins from bursting all balloons between i and j (exclusive)
Step 2 — Base:    dp[i][i+1] = 0 (no balloons between adjacent indices)
Step 3 — Transition:
    dp[i][j] = max over k in (i+1, j-1) of:
        dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
    (burst k last in range, so boundaries are i and j)
Step 4 — Order:   by increasing interval length
Step 5 — Answer:  dp[0][n+1] (padded with 1s at boundaries)

CPP

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    // Pad with 1s at boundaries
    vector<int> a(n + 2);
    a[0] = a[n + 1] = 1;
    for (int i = 0; i < n; i++) a[i + 1] = nums[i];

    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

    for (int len = 2; len <= n + 1; len++) {
        for (int i = 0; i + len <= n + 1; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = max(dp[i][j],
                    dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
            }
        }
    }
    return dp[0][n + 1];
}

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

Pattern 4: DP on Strings

Example: Longest Palindromic Subsequence (LC 516)

Problem: Find the length of the longest palindromic subsequence in a string.

Intuition: If first and last characters match, they're both in the palindrome. Otherwise, try excluding one or the other.

Step 1 — State:   dp[i][j] = length of LPS in s[i..j]
Step 2 — Base:    dp[i][i] = 1 (single character is a palindrome)
Step 3 — Transition:
    If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
    Else:            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
Step 4 — Order:   by increasing length (or i from bottom to top)
Step 5 — Answer:  dp[0][n-1]

Visual for s = "bbbab":

         b    b    b    a    b

  b      1    2    3    3    4
  b      0    1    2    2    3
  b      0    0    1    1    3
  a      0    0    0    1    1
  b      0    0    0    0    1

dp[0][4] = 4 → palindromic subsequence "bbbb"

How dp[0][4] = 4:
  s[0]='b' == s[4]='b' → dp[1][3] + 2 = 2 + 2 = 4

CPP

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j])
                dp[i][j] = dp[i+1][j-1] + 2;
            else
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}

Time: O(n^2) | Space: O(n^2), optimizable to O(n)

Example: Regular Expression Matching (LC 10)

Problem: Implement regex matching with . (any single char) and * (zero or more of the preceding element).

Step 1 — State:   dp[i][j] = does s[0..i-1] match p[0..j-1]?
Step 2 — Base:    dp[0][0] = true
                  dp[0][j] = dp[0][j-2] if p[j-1] == '*' (star eliminates pair)
Step 3 — Transition:
    If p[j-1] == '*':
        dp[i][j] = dp[i][j-2]    (use * as "zero occurrences")
                   OR (if s[i-1] matches p[j-2]):
                   dp[i-1][j]     (use * as "one+ occurrences")
    Else if p[j-1] == '.' or s[i-1] == p[j-1]:
        dp[i][j] = dp[i-1][j-1]  (characters match)
    Else:
        dp[i][j] = false
Step 4 — Order:   row by row, left to right
Step 5 — Answer:  dp[m][n]

Visual for s = "aab", p = "cab":

         ""    c    *    a    *    b

  ""      T    F    T    F    T    F
  a       F    F    F    T    T    F
  a       F    F    F    F    T    F
  b       F    F    F    F    F    T
                                    ↑
                                 answer = true

Explanation:
  c* matches zero c's
  a* matches two a's (first match "a", stay in state, match "a" again)
  b matches b

CPP

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;

    // Base case: empty string vs pattern with *
    for (int j = 2; j <= n; j++) {
        if (p[j-1] == '*')
            dp[0][j] = dp[0][j-2];
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2];  // zero occurrences
                if (p[j-2] == '.' || p[j-2] == s[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j];  // one+ occurrences
                }
            } else if (p[j-1] == '.' || p[j-1] == s[i-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[m][n];
}

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

Example: Wildcard Matching (LC 44)

Problem: Match with ? (any single char) and * (any sequence including empty).

The difference from regex: here * matches any sequence independently (not tied to a preceding character).

Step 1 — State:   dp[i][j] = does s[0..i-1] match p[0..j-1]?
Step 2 — Base:    dp[0][0] = true
                  dp[0][j] = dp[0][j-1] if p[j-1] == '*'
Step 3 — Transition:
    If p[j-1] == '*':
        dp[i][j] = dp[i-1][j]     (* matches current char, continue matching)
                   OR dp[i][j-1]   (* matches empty sequence)
    Else if p[j-1] == '?' or s[i-1] == p[j-1]:
        dp[i][j] = dp[i-1][j-1]
    Else:
        dp[i][j] = false
Step 4 — Order:   row by row, left to right
Step 5 — Answer:  dp[m][n]

CPP

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;

    for (int j = 1; j <= n; j++) {
        if (p[j-1] == '*') dp[0][j] = dp[0][j-1];
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
            } else if (p[j-1] == '?' || s[i-1] == p[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[m][n];
}

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

Example: Palindrome Partitioning II (LC 132)

Problem: Given a string, find the minimum number of cuts to partition it so every substring is a palindrome.

Two-step approach:

Precompute isPalin[i][j] = whether s[i..j] is a palindrome
dp[i] = min cuts for s[0..i]

Step 1 — State:   dp[i] = min cuts for s[0..i]
Step 2 — Base:    dp[i] = i (worst case: cut after every character)
Step 3 — Transition:
    For each j from 0 to i:
        if s[j..i] is a palindrome:
            dp[i] = min(dp[i], (j == 0 ? 0 : dp[j-1] + 1))
Step 4 — Order:   left to right
Step 5 — Answer:  dp[n-1]

CPP

int minCut(string s) {
    int n = s.size();
    // Step 1: Precompute palindrome table
    vector<vector<bool>> isPalin(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i <= 2 || isPalin[i+1][j-1]))
                isPalin[i][j] = true;
        }
    }

    // Step 2: DP for min cuts
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
        if (isPalin[0][i]) {
            dp[i] = 0;  // whole prefix is a palindrome
            continue;
        }
        dp[i] = i;  // worst case
        for (int j = 1; j <= i; j++) {
            if (isPalin[j][i]) {
                dp[i] = min(dp[i], dp[j-1] + 1);
            }
        }
    }
    return dp[n-1];
}

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

Pattern 5: DP with Bitmask

When the state involves subsets of a small set (n <= 20), represent the subset as a bitmask. Bit i being 1 means element i is in the subset.

Example: Traveling Salesman Problem (TSP)

Problem: Visit all n cities exactly once and return to the start, minimizing total distance.

Brute force: Try all n! permutations → too slow for n > 12. Bitmask DP: O(2^n * n^2), feasible for n <= 20.

Step 1 — State:   dp[mask][i] = min cost to visit all cities in 'mask', ending at city i
                  mask is a bitmask: bit j is set if city j has been visited
Step 2 — Base:    dp[1 << 0][0] = 0 (start at city 0, only city 0 visited)
Step 3 — Transition:
    For each mask and each city i in mask:
        For each city j NOT in mask:
            dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j],
                                       dp[mask][i] + dist[i][j])
Step 4 — Order:   by increasing popcount of mask (more cities visited)
Step 5 — Answer:  min over all i of (dp[(1<<n)-1][i] + dist[i][0])
                  (all cities visited, return to start)

Visual for 4 cities (mask has 4 bits):

Cities: 0, 1, 2, 3
Full mask: 1111 (binary) = 15

Starting: dp[0001][0] = 0   (at city 0, visited {0})

Expand city 0 → cities 1, 2, 3:
  dp[0011][1] = dist[0][1]
  dp[0101][2] = dist[0][2]
  dp[1001][3] = dist[0][3]

Expand dp[0011][1] → cities 2, 3:
  dp[0111][2] = dp[0011][1] + dist[1][2]
  dp[1011][3] = dp[0011][1] + dist[1][3]

... continue until all 4 bits are set (mask = 1111) ...

Final: min(dp[1111][i] + dist[i][0]) for i = 0,1,2,3

CPP

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int full = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // start at city 0

    for (int mask = 1; mask <= full; mask++) {
        for (int i = 0; i < n; i++) {
            if (dp[mask][i] == INT_MAX) continue;
            if (!(mask & (1 << i))) continue;  // i not in mask

            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;  // j already visited
                int newMask = mask | (1 << j);
                dp[newMask][j] = min(dp[newMask][j], dp[mask][i] + dist[i][j]);
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (dp[full][i] != INT_MAX) {
            ans = min(ans, dp[full][i] + dist[i][0]);
        }
    }
    return ans;
}

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

Example: Partition Equal Subset Sum (LC 416)

Problem: Given a set of positive integers, determine if it can be partitioned into two subsets with equal sum.

Reduction: This is equivalent to "can we find a subset with sum = totalSum / 2?" which is a subset sum problem (special case of 0/1 knapsack).

Step 1 — State:   dp[s] = true if some subset sums to s
Step 2 — Base:    dp[0] = true (empty subset sums to 0)
Step 3 — Transition: for each num, dp[s] |= dp[s - num]
Step 4 — Order:   for each num, iterate s from target DOWN to num (0/1 knapsack)
Step 5 — Answer:  dp[target] where target = totalSum / 2

CPP

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;
    int target = total / 2;

    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int num : nums) {
        for (int s = target; s >= num; s--) {  // backwards for 0/1
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

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

Example: Target Sum (LC 494)

Problem: Given an array and a target, assign + or - to each element so the expression equals target. Count the number of ways.

Key insight: Let P = elements with +, N = elements with -. Then:

P + N = totalSum
P - N = target
Therefore P = (totalSum + target) / 2

This reduces to: count subsets that sum to (totalSum + target) / 2.

CPP

int findTargetSumWays(vector<int>& nums, int target) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if ((total + target) % 2 != 0 || abs(target) > total) return 0;
    int subsetSum = (total + target) / 2;

    vector<int> dp(subsetSum + 1, 0);
    dp[0] = 1;

    for (int num : nums) {
        for (int s = subsetSum; s >= num; s--) {
            dp[s] += dp[s - num];
        }
    }
    return dp[subsetSum];
}

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

Pattern 6: DP on Trees

Tree DP computes values bottom-up from leaves to root. Each node's DP value depends on its children's values.

Example: House Robber III (LC 337)

Problem: Houses are arranged in a binary tree. You can't rob two directly linked (parent- child) houses. Find the maximum amount.

State: For each node, return a pair: (max if we rob this node, max if we skip this node).

For each node:
  rob_this = node->val + skip(left_child) + skip(right_child)
  skip_this = max(rob, skip) of left + max(rob, skip) of right

         3               rob(3) = 3 + skip(4) + skip(5)
        / \                     = 3 + 0 + 0 = 3 ? No...
       4   5
      / \    \           Let's redo with a bigger example:
     1   3    1
                              3
                             / \
  Left subtree (4):         4   5
    rob(4) = 4+0+0 = 4      / \   \
    skip(4) = max(1,0) +   1   3   1
              max(3,0) = 4
                           rob(1)=1, skip(1)=0
  Right subtree (5):       rob(3)=3, skip(3)=0
    rob(5) = 5+0 = 6
    skip(5) = max(1,0) = 1 rob(4)=4+0+0=4, skip(4)=1+3=4
                           rob(5)=5+0=6, skip(5)=1
  Root (3):
    rob(3) = 3 + skip(4) + skip(5)   rob(3)=3+4+1=8
           = 3 + 4 + 1 = 8           skip(3)=max(4,4)+max(6,1)=4+6=10
    skip(3) = max(4,4) + max(6,1)
            = 4 + 6 = 10             Hmm... skip(3) is not right.
                                     Let me recalculate:
  Answer: max(8, 10) = 10
                                     Actually, skip(3) = max(rob(4), skip(4))
  Picked: skip root(3), take 4,                      + max(rob(5), skip(5))
          skip 4's children,                        = max(4,4) + max(6,1)
          take 5.                                   = 4 + 6 = 10
  Wait: 4 + 5 + 1 = 10?
  Yes: rob 4, rob 5, rob 1 (child     Actually: skip root, then we can
  of 5) = 4 + 5 + 1 = 10              freely choose for children.
  But 4 and 5 are not linked, so OK.   Best: rob(4)=4 + rob(5)=6 = 10?
  Actually 5+1=6 for right subtree.    rob(5)=5+0=5 not 6... Let me redo.
  rob(5) = 5 + skip(1) = 5 + 0 = 5
  skip(5) = max(rob(1), skip(1))
          = max(1, 0) = 1
  skip(3) = max(4,4) + max(5,1) = 4+5 = 9
  rob(3) = 3 + 4 + 1 = 8
  Answer: max(8, 9) = 9
  Explanation: skip root, rob 4, rob 5 → 4+5=9

CPP

pair<int,int> dfs(TreeNode* node) {
    if (!node) return {0, 0};

    auto [rob_left, skip_left] = dfs(node->left);
    auto [rob_right, skip_right] = dfs(node->right);

    int rob_this = node->val + skip_left + skip_right;
    int skip_this = max(rob_left, skip_left) + max(rob_right, skip_right);

    return {rob_this, skip_this};
}

int rob(TreeNode* root) {
    auto [rob_root, skip_root] = dfs(root);
    return max(rob_root, skip_root);
}

Time: O(n) | Space: O(h) where h is tree height (recursion stack)

Pattern 7: State Machine DP

Some problems have multiple "states" at each position (e.g., holding a stock vs not holding). Model each state explicitly.

Example: Best Time to Buy and Sell Stock with Cooldown (LC 309)

Problem: Buy/sell stocks with a 1-day cooldown after selling. Find maximum profit.

States at each day:

IDLE HELD COOL buy sell after cooldown rest rest

Simplify to 3 states:

hold[i] = max profit on day i while holding a stock
idle[i] = max profit on day i while idle (not holding, not in cooldown)
cool[i] = max profit on day i in cooldown (just sold)

hold[i] = max(hold[i-1],    ← keep holding
               idle[i-1] - prices[i])  ← buy today
idle[i] = max(idle[i-1],    ← stay idle
               cool[i-1])   ← cooldown ends
cool[i] = hold[i-1] + prices[i]  ← sell today

CPP

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) return 0;

    int hold = -prices[0];  // bought on day 0
    int idle = 0;           // did nothing
    int cool = 0;           // impossible on day 0, but 0 is safe

    for (int i = 1; i < n; i++) {
        int newHold = max(hold, idle - prices[i]);
        int newIdle = max(idle, cool);
        int newCool = hold + prices[i];
        hold = newHold;
        idle = newIdle;
        cool = newCool;
    }
    return max(idle, cool);
}

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

Example: Distinct Subsequences (LC 115)

Problem: Given strings s and t, count the number of distinct subsequences of s that equal t.

Step 1 — State:   dp[i][j] = number of ways to form t[0..j-1] from s[0..i-1]
Step 2 — Base:    dp[i][0] = 1 for all i (empty t: one way — choose nothing)
                  dp[0][j] = 0 for j > 0 (empty s can't form non-empty t)
Step 3 — Transition:
    If s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1]  (use s[i-1] to match t[j-1])
                 + dp[i-1][j]     (skip s[i-1], don't use it)
    Else:
        dp[i][j] = dp[i-1][j]    (s[i-1] can't match, must skip it)
Step 4 — Order:   row by row
Step 5 — Answer:  dp[m][n]

Visual for s = "rabbbit", t = "rabbit":

         ""   r   a   b   b   i   t

  ""      1    0   0   0   0   0   0
  r       1    1   0   0   0   0   0
  a       1    1   1   0   0   0   0
  b       1    1   1   1   0   0   0
  b       1    1   1   2   1   0   0
  b       1    1   1   3   3   0   0
  i       1    1   1   3   3   3   0
  t       1    1   1   3   3   3   3
                                    ↑
                                 answer = 3

The three "b"s in "rabbbit" can be matched to the two "b"s in "rabbit"
in C(3,2) = 3 ways:
  ra[b][b]_it, ra[b]_[b]it, ra_[b][b]it
  (where [] means selected, _ means skipped)

CPP

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][0] = 1;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j];
            if (s[i-1] == t[j-1])
                dp[i][j] += dp[i-1][j-1];
        }
    }
    return dp[m][n];
}

Time: O(m * n) | Space: O(m * n), optimizable to O(n)

Space Optimization Techniques

1. Rolling Array (Two Rows)

When dp[i] only depends on dp[i-1], keep only two rows and alternate.

Instead of: dp[n][m]
Use:        dp[2][m]

Access pattern:
  curr = i % 2
  prev = (i-1) % 2  or  1 - curr
  dp[curr][j] = f(dp[prev][...])

2. Single Row (1D from 2D)

For 0/1 knapsack: iterate capacity backwards to prevent using updated values. For unbounded knapsack: iterate forwards (reuse is allowed).

3. State Compression with Bitmask

When tracking which elements are "used" in a subset of size n <= 20:

CPP

int mask = 0;
mask |= (1 << i);    // add element i
mask &= ~(1 << i);   // remove element i
if (mask & (1 << i)) // check if element i is in set
int count = __builtin_popcount(mask);  // count elements in set

4. Variables Instead of Arrays

When dp[i] depends on a fixed number of previous states:

Fibonacci: dp[i] = dp[i-1] + dp[i-2]  →  two variables
House Robber: same pattern               →  two variables
Climbing Stairs: same pattern             →  two variables

How to Identify DP Problems

Strong Indicators

"Count the number of ways..." → counting DP
"Find the minimum/maximum..." with choices → optimization DP
"Is it possible to..." → boolean DP
"Longest/shortest..." sequence with constraints → sequence DP

Structural Indicators

Problem has optimal substructure (optimal solution built from optimal sub-solutions)
Overlapping subproblems (same subproblem computed multiple times in recursion)
Choices at each step that affect future options
Greedy fails (can construct a counterexample)

Decision Flowchart

Common Mistakes

1. Wrong Base Cases

Example: Coin change
WRONG:  dp[0] = 1   (that's for counting WAYS, not minimum COINS)
RIGHT:  dp[0] = 0   (zero coins for zero amount)

2. Wrong Iteration Order

0/1 Knapsack with 1D array:
WRONG:  for w = weight[i] to W    (reuses items — unbounded knapsack!)
RIGHT:  for w = W down to weight[i]

3. Off-by-One Errors

State:  dp[i] = answer for first i characters (NOT s[i])
Then:   dp[0] = base case (empty string)
        dp[n] = answer for full string
        Access s[i-1] when computing dp[i]

4. Forgetting to Initialize

For min problems: initialize dp to INT_MAX or a large value
For max problems: initialize dp to 0 or INT_MIN
For counting: initialize dp to 0 (except base cases)
For boolean: initialize dp to false (except base cases)

5. Not Considering All Transitions

LCS: forgetting the case when characters don't match
Edit Distance: forgetting one of the three operations
Interval DP: not iterating over ALL split points k

Classic DP Problems for Google Interviews — Quick Reference

#	Problem	Pattern	Key Insight
1	Coin Change (322)	1D	Unbounded knapsack variant
2	Word Break (139)	1D	Check all dictionary words as last word
3	Decode Ways (91)	1D	Fibonacci-like with conditions
4	LPS (516)	Interval	Expand from center or 2D on [i,j]
5	Kadane's (53)	1D	Extend or restart at each position
6	Stock w/ Cooldown (309)	State Machine	Track hold/idle/cool states
7	Partition Equal Subset (416)	Bitmask/Knapsack	Reduce to subset sum
8	Target Sum (494)	Knapsack	Math reduces to subset sum
9	Min Path Sum (64)	2D Grid	Standard grid DP
10	Distinct Subsequences (115)	2D String	Match or skip current char

All ten problems have been covered with full explanations, state definitions, transitions, visual tables, and complete C++ code in this guide.

Summary: The DP Mindset

Practice strategy: Start with 1D DP until comfortable, then 2D, then interval/bitmask. For each problem, always write the 5-step framework before coding. The framework IS the solution — the code just translates it.