Pattern 5: State Machine DP Problems

The Mode Transition Pattern: At each position i, track different states/modes. Transitions between states have costs/constraints. State represents "what mode/condition am I in?"

---

The Core Pattern

THE MENTAL MODEL

Imagine you're playing a video game character that has different modes:

1. At each step, your character is in a specific state (flying, walking, swimming)
2. You can transition between states (walking → jumping)
3. Some transitions are forbidden or have costs
4. Your current state determines what you can do next
5. You want to find the optimal sequence of state transitions

This is State Machine DP.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "can't do X twice in a row", "holding/not holding", "at most k", "mode", "state", "last choice matters"

Structure:

• Linear progression through positions (like Pattern 1)
• But current decision depends on previous state/mode
• Multiple "versions" of yourself at each position

State: dp[i][state] = "best answer at position i when in state/mode"

Transition: From each state, can only move to certain other states:

dp[i][new_state] = best of all (
    dp[i-1][old_state] + transition_cost
) for valid old_state → new_state transitions

---

Category 1: Stock Trading Problems

1. Best Time to Buy and Sell Stock II (LC 122)

PROBLEM

You are given an integer array prices where prices[i] is the price of a given stock on day i.

You can buy and sell the stock unlimited times, but you can only hold at most one share at a time.

Return the maximum profit you can achieve.

State Definition:

• dp[i][0] = max profit on day i when not holding stock
• dp[i][1] = max profit on day i when holding stock

State Transitions:

not_holding (0) ←→ holding (1)
   ↑ sell           buy ↓

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];

    // Base case: day 0
    dp[0][0] = 0;           // not holding: no profit
    dp[0][1] = -prices[0];  // holding: paid for stock

    for (int i = 1; i < n; i++) {
        // Not holding: either already not holding, or sell today
        dp[i][0] = Math.max(
            dp[i-1][0],              // already not holding
            dp[i-1][1] + prices[i]   // sell today
        );

        // Holding: either already holding, or buy today
        dp[i][1] = Math.max(
            dp[i-1][1],              // already holding
            dp[i-1][0] - prices[i]   // buy today
        );
    }

    return dp[n-1][0];  // must end not holding
}

THE FOUNDATION OF STATE MACHINE DP

Two states: not_holding and holding

Transitions:

• not_holding → not_holding (rest)
• not_holding → holding (buy)
• holding → holding (rest)
• holding → not_holding (sell)

Each transition has a cost/gain!

Space Optimized (O(1)):

public int maxProfit(int[] prices) {
    int notHolding = 0;
    int holding = -prices[0];

    for (int i = 1; i < prices.length; i++) {
        int newNotHolding = Math.max(notHolding, holding + prices[i]);
        int newHolding = Math.max(holding, notHolding - prices[i]);
        notHolding = newNotHolding;
        holding = newHolding;
    }

    return notHolding;
}

---

2. Best Time to Buy and Sell Stock III (LC 123)

PROBLEM

You are given an array prices. You can complete at most two transactions.

Note: You cannot engage in multiple transactions simultaneously (must sell before buying again).

State Definition:

• dp[i][k][0] = max profit on day i with at most k transactions, not holding
• dp[i][k][1] = max profit on day i with at most k transactions, holding

Where k = number of transactions completed (a transaction = buy + sell)

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][][] dp = new int[n][3][2];  // at most 2 transactions

    // Base case: impossible states
    for (int k = 0; k <= 2; k++) {
        dp[0][k][0] = 0;
        dp[0][k][1] = -prices[0];
    }

    for (int i = 1; i < n; i++) {
        for (int k = 0; k <= 2; k++) {
            // Not holding
            dp[i][k][0] = Math.max(
                dp[i-1][k][0],           // rest
                dp[i-1][k][1] + prices[i] // sell (completes transaction)
            );

            // Holding
            if (k > 0) {
                dp[i][k][1] = Math.max(
                    dp[i-1][k][1],           // rest
                    dp[i-1][k-1][0] - prices[i]  // buy (starts new transaction)
                );
            } else {
                dp[i][k][1] = dp[i-1][k][1];  // can't buy if no transactions left
            }
        }
    }

    return dp[n-1][2][0];
}

3D STATE MACHINE!

State: [day][transactions_left][holding_status]

Three dimensions:

1. Position (day)
2. Transactions remaining
3. Holding or not

Complexity: O(n × k × 2) = O(nk)

---

3. Best Time to Buy and Sell Stock IV (LC 188)

State Definition: dp[i][k][holding] = max profit at day i with at most k transactions

Generalization of Stock III: Same logic, but with arbitrary k

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (n == 0 || k == 0) return 0;

    // Optimization: if k >= n/2, it's unlimited transactions
    if (k >= n / 2) {
        return maxProfitUnlimited(prices);
    }

    int[][][] dp = new int[n][k + 1][2];

    // Base case
    for (int t = 0; t <= k; t++) {
        dp[0][t][0] = 0;
        dp[0][t][1] = -prices[0];
    }

    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= k; t++) {
            dp[i][t][0] = Math.max(
                dp[i-1][t][0],
                dp[i-1][t][1] + prices[i]
            );

            if (t > 0) {
                dp[i][t][1] = Math.max(
                    dp[i-1][t][1],
                    dp[i-1][t-1][0] - prices[i]
                );
            } else {
                dp[i][t][1] = Integer.MIN_VALUE / 2;
            }
        }
    }

    return dp[n-1][k][0];
}

private int maxProfitUnlimited(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        profit += Math.max(0, prices[i] - prices[i-1]);
    }
    return profit;
}

---

4. Best Time to Buy and Sell Stock with Cooldown (LC 309)

PROBLEM

After you sell your stock, you cannot buy stock on the next day (cooldown 1 day).

State Definition:

• dp[i][0] = max profit on day i, holding stock
• dp[i][1] = max profit on day i, not holding, can buy
• dp[i][2] = max profit on day i, cooldown (just sold)

State Transitions:

holding (0) → cooldown (2) [sell]
cooldown (2) → not_holding (1) [cooldown expires]
not_holding (1) → holding (0) [buy]

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n <= 1) return 0;

    int[][] dp = new int[n][3];
    // State 0: holding, 1: not holding (can buy), 2: cooldown

    dp[0][0] = -prices[0];  // buy on day 0
    dp[0][1] = 0;           // don't do anything
    dp[0][2] = 0;           // can't sell on day 0

    for (int i = 1; i < n; i++) {
        // Holding: either already holding, or buy today (from not_holding)
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);

        // Not holding: either already not holding, or cooldown expired
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][2]);

        // Cooldown: sold today (from holding)
        dp[i][2] = dp[i-1][0] + prices[i];
    }

    return Math.max(dp[n-1][1], dp[n-1][2]);
}

STATE TRANSITION DIAGRAM

         ┌─────────┐
         │ holding │
         └─────────┘
              ↓ sell (+price)
         ┌──────────┐
         │ cooldown │
         └──────────┘
              ↓ (automatic)
       ┌──────────────┐
       │ not_holding  │
       └──────────────┘
              ↓ buy (-price)
         [back to holding]

Three states instead of two!

---

5. Best Time to Buy and Sell Stock with Transaction Fee (LC 714)

State Definition: dp[i][holding] with transaction fee on sell

Transition: Same as Stock II, but subtract fee when selling

public int maxProfit(int[] prices, int fee) {
    int n = prices.length;
    int notHolding = 0;
    int holding = -prices[0];

    for (int i = 1; i < n; i++) {
        int newNotHolding = Math.max(
            notHolding,
            holding + prices[i] - fee  // sell with fee
        );
        int newHolding = Math.max(
            holding,
            notHolding - prices[i]  // buy
        );
        notHolding = newNotHolding;
        holding = newHolding;
    }

    return notHolding;
}

---

Category 2: Coloring/Choice Problems

6. Paint House (LC 256)

PROBLEM

There are n houses in a row. Each house can be painted with one of three colors: red, blue, or green.

The cost of painting each house with a certain color is different. You must paint all houses such that no two adjacent houses have the same color.

Return the minimum cost to paint all houses.

State Definition:

• dp[i][0] = min cost to paint houses 0..i with house i being red
• dp[i][1] = min cost to paint houses 0..i with house i being blue
• dp[i][2] = min cost to paint houses 0..i with house i being green

State Transitions: Can't use same color twice in a row

public int minCost(int[][] costs) {
    int n = costs.length;
    int[][] dp = new int[n][3];

    // Base case: first house
    dp[0][0] = costs[0][0];
    dp[0][1] = costs[0][1];
    dp[0][2] = costs[0][2];

    for (int i = 1; i < n; i++) {
        // Paint house i red: previous must be blue or green
        dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];

        // Paint house i blue: previous must be red or green
        dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];

        // Paint house i green: previous must be red or blue
        dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
    }

    return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
}

STATE TRANSITIONS VISUALIZED

Red (0) ──┐
          ├─→ Blue (1)
Green(2)──┘

Blue (1) ──┐
           ├─→ Red (0)
Green (2)──┘

Red (0) ───┐
           ├─→ Green (2)
Blue (1) ──┘

Rule: From any color, can transition to any OTHER color.

---

7. Paint House II (LC 265)

State Definition: dp[i][color] with k colors

Transition: From any color, can go to any OTHER color

public int minCostII(int[][] costs) {
    int n = costs.length;
    int k = costs[0].length;
    int[][] dp = new int[n][k];

    // Base case
    for (int c = 0; c < k; c++) {
        dp[0][c] = costs[0][c];
    }

    for (int i = 1; i < n; i++) {
        for (int c = 0; c < k; c++) {
            dp[i][c] = Integer.MAX_VALUE;
            // Try all previous colors except c
            for (int prevC = 0; prevC < k; prevC++) {
                if (prevC != c) {
                    dp[i][c] = Math.min(dp[i][c], dp[i-1][prevC] + costs[i][c]);
                }
            }
        }
    }

    int minCost = Integer.MAX_VALUE;
    for (int c = 0; c < k; c++) {
        minCost = Math.min(minCost, dp[n-1][c]);
    }
    return minCost;
}

OPTIMIZATION FOR PAINT HOUSE II

Observation: We only need the minimum and second minimum from previous row.

• If current color ≠ color of minimum → use minimum
• If current color = color of minimum → use second minimum

Time: O(n × k × k) → O(n × k) with optimization

---

8. Paint Fence (LC 276)

State Definition:

• dp[i][0] = ways to paint fence up to post i where post i is different color from i-1
• dp[i][1] = ways to paint fence up to post i where post i is same color as i-1

Constraint: Can't have 3+ consecutive posts with same color

public int numWays(int n, int k) {
    if (n == 0) return 0;
    if (n == 1) return k;

    int[][] dp = new int[n][2];
    // State 0: different from previous
    // State 1: same as previous

    dp[0][0] = k;  // first post: k choices
    dp[0][1] = 0;  // can't be same as non-existent previous

    dp[1][0] = k * (k - 1);  // different from first
    dp[1][1] = k;            // same as first

    for (int i = 2; i < n; i++) {
        // Different: can come from either state
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * (k - 1);

        // Same: can ONLY come from "different" state
        // (to avoid 3 consecutive)
        dp[i][1] = dp[i-1][0];
    }

    return dp[n-1][0] + dp[n-1][1];
}

CONSTRAINT ENFORCEMENT

Rule: Can't have 3 consecutive same colors.

Enforcement: same state can ONLY come from different state.

This prevents same → same → same transitions!

---

9. Count Number of Ways to Place Houses (LC 2320)

State Definition:

• dp[i][0] = ways to place on i plots with plot i being empty
• dp[i][1] = ways to place on i plots with plot i having a house

Constraint: Can't place houses adjacently

public int countHousePlacements(int n) {
    long MOD = 1_000_000_007;
    long[][] dp = new long[n][2];

    dp[0][0] = 1;  // empty
    dp[0][1] = 1;  // house

    for (int i = 1; i < n; i++) {
        // Empty: can come from both states
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD;

        // House: can ONLY come from empty
        dp[i][1] = dp[i-1][0];
    }

    long oneSide = (dp[n-1][0] + dp[n-1][1]) % MOD;

    // Both sides of street are independent
    return (int)((oneSide * oneSide) % MOD);
}

TWO INDEPENDENT STATE MACHINES

The street has two sides. Each side is an independent state machine.

Total ways = (ways for one side) × (ways for other side)

---

10. Domino and Tromino Tiling (LC 790)

State Definition:

• dp[i][0] = ways to fully tile up to column i
• dp[i][1] = ways with partial tile (top hanging)
• dp[i][2] = ways with partial tile (bottom hanging)

Transition: Based on tile placement rules

public int numTilings(int n) {
    long MOD = 1_000_000_007;
    long[][] dp = new long[n + 1][3];

    dp[0][0] = 1;
    dp[1][0] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]) % MOD;
        dp[i][1] = (dp[i-2][0] + dp[i-1][2]) % MOD;
        dp[i][2] = (dp[i-2][0] + dp[i-1][1]) % MOD;
    }

    return (int)dp[n][0];
}

---

Category 3: Rolling Constraints

11. Dice Roll Simulation (LC 1223)

PROBLEM

You have a die with n faces numbered 1 to n. You roll the die rollMax[i] times. However, you cannot roll number i more than rollMax[i] consecutive times.

Return the number of distinct sequences you can obtain.

State Definition:

• dp[rolls][last_num][consecutive] = ways to make rolls rolls
  • Ending with last_num
  • With consecutive occurrences of last_num at the end

public int dieSimulator(int n, int[] rollMax) {
    long MOD = 1_000_000_007;
    int maxRoll = 15;  // max rollMax value
    long[][][] dp = new long[n + 1][7][maxRoll + 1];
    // dp[rolls][last_number][consecutive_count]

    // Base case: 1 roll
    for (int num = 1; num <= 6; num++) {
        dp[1][num][1] = 1;
    }

    for (int roll = 2; roll <= n; roll++) {
        for (int num = 1; num <= 6; num++) {
            for (int prevNum = 1; prevNum <= 6; prevNum++) {
                for (int cons = 1; cons <= rollMax[prevNum - 1]; cons++) {
                    if (num == prevNum) {
                        // Same number: increment consecutive count
                        if (cons + 1 <= rollMax[num - 1]) {
                            dp[roll][num][cons + 1] += dp[roll - 1][prevNum][cons];
                            dp[roll][num][cons + 1] %= MOD;
                        }
                    } else {
                        // Different number: reset consecutive to 1
                        dp[roll][num][1] += dp[roll - 1][prevNum][cons];
                        dp[roll][num][1] %= MOD;
                    }
                }
            }
        }
    }

    long result = 0;
    for (int num = 1; num <= 6; num++) {
        for (int cons = 1; cons <= rollMax[num - 1]; cons++) {
            result += dp[n][num][cons];
            result %= MOD;
        }
    }

    return (int)result;
}

3D STATE WITH ROLLING CONSTRAINT

State: [rolls_made][last_number][consecutive_count]

Constraint: consecutive_count ≤ rollMax[number]

This tracks both what number AND how many times in a row!

---

12. Knight Dialer (LC 935)

State Definition:

• dp[i][digit] = number of ways to dial i numbers ending at digit

Transition: Knight moves on phone keypad

public int knightDialer(int n) {
    long MOD = 1_000_000_007;
    int[][] moves = {
        {4, 6},     // from 0
        {6, 8},     // from 1
        {7, 9},     // from 2
        {4, 8},     // from 3
        {0, 3, 9},  // from 4
        {},         // from 5 (no valid moves)
        {0, 1, 7},  // from 6
        {2, 6},     // from 7
        {1, 3},     // from 8
        {2, 4}      // from 9
    };

    long[][] dp = new long[n][10];

    // Base case: 1 number
    for (int digit = 0; digit <= 9; digit++) {
        dp[0][digit] = 1;
    }

    for (int i = 1; i < n; i++) {
        for (int digit = 0; digit <= 9; digit++) {
            // Try all possible previous digits
            for (int prev = 0; prev <= 9; prev++) {
                for (int nextDigit : moves[prev]) {
                    if (nextDigit == digit) {
                        dp[i][digit] += dp[i-1][prev];
                        dp[i][digit] %= MOD;
                    }
                }
            }
        }
    }

    long result = 0;
    for (int digit = 0; digit <= 9; digit++) {
        result += dp[n-1][digit];
        result %= MOD;
    }

    return (int)result;
}

GRAPH-BASED STATE MACHINE

States = digits 0-9

Transitions = knight moves on keypad:

1 → {6, 8}
2 → {7, 9}
3 → {4, 8}
etc.

Each digit has limited valid next digits!

---

13. Number of Music Playlists (LC 920)

State Definition:

• dp[i][j] = number of playlists of length i using exactly j unique songs
  • With constraint: k-gap between replays

public int numMusicPlaylists(int n, int goal, int k) {
    long MOD = 1_000_000_007;
    long[][] dp = new long[goal + 1][n + 1];

    dp[0][0] = 1;

    for (int i = 1; i <= goal; i++) {
        for (int j = 1; j <= Math.min(i, n); j++) {
            // Play a new song
            dp[i][j] += dp[i-1][j-1] * (n - (j - 1));

            // Replay an old song (if we have more than k songs)
            if (j > k) {
                dp[i][j] += dp[i-1][j] * (j - k);
            }

            dp[i][j] %= MOD;
        }
    }

    return (int)dp[goal][n];
}

---

14. Count Ways to Build Good Strings (LC 2466)

State Definition: dp[length] = ways to build string of exact length

Constraint: Must use zero and one counts within bounds

---

15. Number of Ways to Stay in the Same Place After Some Steps (LC 1269)

State Definition:

• dp[i][pos] = ways to be at position pos after i steps

Transition: From each position, can move left, right, or stay

public int numWays(int steps, int arrLen) {
    long MOD = 1_000_000_007;
    int maxPos = Math.min(steps / 2 + 1, arrLen);  // optimization
    long[][] dp = new long[steps + 1][maxPos];

    dp[0][0] = 1;

    for (int i = 1; i <= steps; i++) {
        for (int pos = 0; pos < maxPos; pos++) {
            // Stay
            dp[i][pos] = dp[i-1][pos];

            // Move left (from pos+1)
            if (pos + 1 < maxPos) {
                dp[i][pos] += dp[i-1][pos + 1];
            }

            // Move right (from pos-1)
            if (pos > 0) {
                dp[i][pos] += dp[i-1][pos - 1];
            }

            dp[i][pos] %= MOD;
        }
    }

    return (int)dp[steps][0];
}

---

Category 4: Binary/Mode Switching

16. Flip String to Monotone Increasing (LC 926)

PROBLEM

A binary string is monotone increasing if it consists of some number of 0's followed by some number of 1's.

Return the minimum number of flips to make s monotone increasing.

State Definition:

• dp[i][0] = min flips for first i characters, ending in all 0s
• dp[i][1] = min flips for first i characters, started 1s (can have 0s before)

public int minFlipsMonoIncr(String s) {
    int n = s.length();
    int[][] dp = new int[n + 1][2];

    for (int i = 1; i <= n; i++) {
        char c = s.charAt(i - 1);

        // State 0: all zeros so far
        dp[i][0] = dp[i-1][0] + (c == '1' ? 1 : 0);

        // State 1: started ones (monotone increasing)
        dp[i][1] = Math.min(
            dp[i-1][1] + (c == '0' ? 1 : 0),  // already in "1s" mode
            dp[i-1][0]                         // transition from "0s" to "1s"
        );
    }

    return Math.min(dp[n][0], dp[n][1]);
}

TWO MODES

Mode 0: Still in the "all zeros" phase Mode 1: Started the "ones" phase (can't go back to 0s)

Transition: One-way from mode 0 → mode 1

---

17. Maximum Alternating Subsequence Sum (LC 1911)

State Definition:

• dp[i][0] = max sum at position i with even-indexed elements (positive)
• dp[i][1] = max sum at position i with odd-indexed elements (negative)

public long maxAlternatingSum(int[] nums) {
    int n = nums.length;
    long[][] dp = new long[n + 1][2];

    for (int i = 1; i <= n; i++) {
        // Even index (add positive)
        dp[i][0] = Math.max(
            dp[i-1][0],              // don't take
            dp[i-1][1] + nums[i-1]   // take (from odd state)
        );

        // Odd index (subtract)
        dp[i][1] = Math.max(
            dp[i-1][1],              // don't take
            dp[i-1][0] - nums[i-1]   // take (from even state)
        );
    }

    return dp[n][0];  // must end on even (positive)
}

ALTERNATING STATES

States alternate: even (+) ↔ odd (-)

Must end in even state (positive contribution)

---

18. Minimize Malware Spread (LC 924/928)

State Definition: dp[node][infected_state] tracking infection propagation

States: clean, infected, removed

Transition: Infection spreads based on graph structure

---

19. Maximum Score from Performing Multiplication Operations (LC 1770)

State Definition:

• dp[i][left_taken] = max score after i operations
  • Having taken left_taken elements from the left
  • (implicitly i - left_taken from the right)

public int maximumScore(int[] nums, int[] multipliers) {
    int n = nums.length;
    int m = multipliers.length;
    int[][] dp = new int[m + 1][m + 1];

    for (int i = m - 1; i >= 0; i--) {
        for (int left = i; left >= 0; left--) {
            int right = n - 1 - (i - left);

            // Take from left
            int takeLeft = multipliers[i] * nums[left] + dp[i + 1][left + 1];

            // Take from right
            int takeRight = multipliers[i] * nums[right] + dp[i + 1][left];

            dp[i][left] = Math.max(takeLeft, takeRight);
        }
    }

    return dp[0][0];
}

---

20. Delete and Earn (LC 740)

State Definition:

• dp[num][0] = max points up to number num, didn't take num
• dp[num][1] = max points up to number num, took num

Constraint: If you take num, you can't take num-1 or num+1

public int deleteAndEarn(int[] nums) {
    int maxNum = 0;
    for (int num : nums) maxNum = Math.max(maxNum, num);

    int[] points = new int[maxNum + 1];
    for (int num : nums) {
        points[num] += num;  // sum all occurrences
    }

    int[][] dp = new int[maxNum + 1][2];
    // State 0: didn't take, State 1: took

    for (int num = 1; num <= maxNum; num++) {
        // Don't take num
        dp[num][0] = Math.max(dp[num-1][0], dp[num-1][1]);

        // Take num (can't use num-1)
        dp[num][1] = dp[num-1][0] + points[num];
    }

    return Math.max(dp[maxNum][0], dp[maxNum][1]);
}

HOUSE ROBBER VARIANT

This is House Robber applied to numbers!

• If you "rob" number k, you get k × count[k] points
• But you can't rob k-1 or k+1

Same state machine structure!

---

The Common Thread

WHAT MAKES THESE ALL THE SAME PATTERN?

Every problem has:

1. State dimension: dp[i][state] where state = "what mode/condition am I in?"
2. States are mutually exclusive: At position i, you're in exactly ONE state
3. Transitions have rules: Can only go from certain states to certain others
4. Cost/value per transition: Each state transition may have different costs
5. Goal: Optimize across all valid state transitions

Key Insight: When the optimal choice at position i depends not just on i but on what happened before i (beyond just the value), you need state machine DP. The state encodes the relevant history.

---

Classic Loop Structure

// Initialize base states
for (State s : validStates) {
    dp[0][s] = baseValue[s];
}

// Process each position
for (int i = 1; i < n; i++) {
    for (State currentState : validStates) {
        // Try transitioning from all valid previous states
        for (State prevState : validTransitions[currentState]) {
            dp[i][currentState] = best(
                dp[i][currentState],
                dp[i-1][prevState] + transitionCost(prevState, currentState, i)
            );
        }
    }
}

// Answer is best final state
return max(dp[n-1][state] for all states);

---

Pattern Recognition Keywords

KEY PATTERNS TO RECOGNIZE

"Can't do X two times in a row" → Track previous choice as state

"At most k of something" → k is part of state

"Holding vs not holding" → Binary state

"What was my last choice?" → Last choice is the state

"Different costs depending on history" → History encoded as state

"Mode switching" → Each mode is a state

"Consecutive constraint" → Track consecutive count in state

---

Pattern Recognition Checklist

USE THIS CHECKLIST

When you see a new problem, ask:

• Does the current decision depend on previous state/mode?
• Are there multiple "versions" of the answer at each position?
• Do I have constraints on transitions (can't do X after Y)?
• Do I need to track "what mode/condition am I in"?
• Does the problem mention "consecutive", "alternating", or "can't repeat"?

If YES to 2+ → Pattern 5: State Machine DP

---

Common Mistakes

COMMON PITFALLS

Mistake 1: Not identifying all states

// WRONG - missing states
dp[i][holding];  // only 2 states

// RIGHT - need 3 states for cooldown
dp[i][holding];
dp[i][not_holding];
dp[i][cooldown];

Mistake 2: Invalid state transitions

// WRONG - allowing invalid transitions
dp[i][same] = dp[i-1][same];  // 3 consecutive same!

// RIGHT - enforce constraint
dp[i][same] = dp[i-1][different];  // can only come from different

Mistake 3: Forgetting to check all end states

// WRONG - only checking one state
return dp[n][0];

// RIGHT - check all valid end states
return Math.max(dp[n][0], dp[n][1]);

Mistake 4: State space explosion

// Too many states? Consider:
// 1. Can some states be combined?
// 2. Is there redundant information?
// 3. Can you use a different state definition?

---

Space Optimization

FROM O(n × states) TO O(states)

Since each position only depends on the previous position, you can use rolling array:

Before:

int[][] dp = new int[n][numStates];

After:

int[] prev = new int[numStates];
int[] curr = new int[numStates];

for (int i = 1; i < n; i++) {
    // Compute curr from prev
    // ...
    // Swap
    int[] temp = prev;
    prev = curr;
    curr = temp;
}

Or even simpler (direct variable tracking):

int holding = -prices[0];
int notHolding = 0;

for (int i = 1; i < n; i++) {
    int newHolding = Math.max(holding, notHolding - prices[i]);
    int newNotHolding = Math.max(notHolding, holding + prices[i]);
    holding = newHolding;
    notHolding = newNotHolding;
}

---

State Transition Diagram Examples

Stock Trading (2 States)

┌──────────────┐                 ┌──────────────┐
│ Not Holding  │ ─────────────→  │   Holding    │
│   (profit)   │   buy (-price)  │ (profit-cost)│
└──────────────┘                 └──────────────┘
       ↑                                  │
       └──────────────────────────────────┘
              sell (+price)

Stock with Cooldown (3 States)

┌──────────────┐
│   Holding    │
└──────────────┘
       │ sell
       ↓
┌──────────────┐
│  Cooldown    │
└──────────────┘
       │ (automatic)
       ↓
┌──────────────┐
│ Not Holding  │ ────┐
└──────────────┘     │
       ↑             │ buy
       └─────────────┘

Paint Fence (2 States)

┌───────────────┐                ┌───────────────┐
│   Different   │ ──────────→    │     Same      │
│  (prev color) │  (paint same)  │  (prev color) │
└───────────────┘                └───────────────┘
       ↑                                  │
       └──────────────────────────────────┘
         (paint different, k-1 choices)

       ┌─────────────────────────┐
       │  paint different        │
       │  (k-1 choices)          │
       └─────────────────────────┘

---

Learning Path

RECOMMENDED ORDER

Week 1: Stock Trading (Problems 1-5)

• Master binary states (holding/not holding)
• Learn transaction counting
• Understand cooldown mechanics

Week 2: Coloring (Problems 6-10)

• Multiple states (colors)
• Consecutive constraints
• Independent state machines

Week 3: Rolling Constraints (Problems 11-15)

• Complex state tracking
• Consecutive count in state
• Graph-based transitions

Week 4: Advanced (Problems 16-20)

• Mode switching
• Game theory with states
• Multi-dimensional state

Total: 20 problems × 4 weeks = Pattern 5 mastery

---

Quick Reference Table

Problem	States	Transition Rule	Pattern Type
Stock II	holding, not_holding	buy, sell, hold	Binary mode
Stock Cooldown	holding, not_holding, cooldown	forced cooldown after sell	3-state cycle
Paint House	red, blue, green	can't repeat color	Color choice
Paint Fence	same, different	max 2 consecutive same	Consecutive limit
Dice Simulation	[last_num][consecutive]	rollMax constraint	Rolling constraint
Knight Dialer	digit 0-9	knight moves	Graph transitions
Flip Monotone	all_0s, started_1s	one-way transition	Mode switch
Alternating Sum	even_index, odd_index	alternating signs	Binary alternating

---

Next Steps

AFTER MASTERING PATTERN 5

You've now mastered the 5 core DP patterns!

Ready for:

• DP on Trees (Pattern 6 - hierarchical states)
• Bitmask DP (Pattern 7 - subset states)
• Advanced Multi-dimensional DP

Connection to Previous Patterns:

• Pattern 1: 1D state (position only)
• Pattern 2: 2D state (two positions)
• Pattern 3: 2D state (items + resource)
• Pattern 4: 2D state (range endpoints)
• Pattern 5: 2D state (position + mode) ← Mode matters!

---

Final Thoughts

STATE MACHINE DP IS THE "MODE" PATTERN

State Machine DP teaches you to think about modes and transitions.

Master these 20 problems, and you'll:

• Recognize when state/mode matters instantly
• Design proper state spaces
• Handle complex constraints through states
• See stock, coloring, and game problems as state machines

This is your mode-based foundation. Build it strong.

---

Summary: The State Machine Template

// Template for State Machine DP
public int stateMachineDP(int[] arr) {
    int n = arr.length;
    int numStates = /* number of states */;
    int[][] dp = new int[n][numStates];

    // Base case: initialize all states at position 0
    for (int s = 0; s < numStates; s++) {
        dp[0][s] = baseValue(s, arr[0]);
    }

    // Process each position
    for (int i = 1; i < n; i++) {
        for (int curr = 0; curr < numStates; curr++) {
            dp[i][curr] = initValue;  // MAX_VALUE for min, MIN_VALUE for max

            // Try all valid transitions
            for (int prev = 0; prev < numStates; prev++) {
                if (canTransition(prev, curr)) {
                    dp[i][curr] = best(
                        dp[i][curr],
                        dp[i-1][prev] + transitionCost(prev, curr, arr[i])
                    );
                }
            }
        }
    }

    // Return best final state
    int result = initValue;
    for (int s = 0; s < numStates; s++) {
        result = best(result, dp[n-1][s]);
    }
    return result;
}

REMEMBER THE MANTRA

"At each position, I'm in a specific state/mode. From each state, I can transition to certain other states with specific costs. Find the optimal sequence of state transitions."

This is the essence of State Machine DP.