State Machine DP

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;
    for (int price : prices) {
        minPrice   = Math.min(minPrice, price);
        maxProfit  = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

// States: hold (own stock), free (don't own)
// hold[i] = max profit on day i while holding
// free[i] = max profit on day i while not holding

public int maxProfit(int[] prices) {
    int hold = -prices[0], free = 0;
    for (int i = 1; i < prices.length; i++) {
        hold = Math.max(hold, free - prices[i]); // buy or keep holding
        free = Math.max(free, hold + prices[i]); // sell or stay free
    }
    return free;
}

// States: hold, sold (cooldown), free
public int maxProfitWithCooldown(int[] prices) {
    int hold = -prices[0], sold = 0, free = 0;
    for (int i = 1; i < prices.length; i++) {
        int prevHold = hold, prevSold = sold, prevFree = free;
        hold = Math.max(prevHold, prevFree - prices[i]);  // buy (can't buy from sold/cooldown)
        sold = prevHold + prices[i];                       // sell (enters cooldown)
        free = Math.max(prevFree, prevSold);               // stay free or exit cooldown
    }
    return Math.max(sold, free);
}

public int maxProfitK(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) return maxProfitUnlimited(prices);
    // dp[t][0] = max profit with t transactions, not holding
    // dp[t][1] = max profit with t transactions, holding
    int[][] dp = new int[k+1][2];
    for (int t = 1; t <= k; t++) dp[t][1] = -prices[0];

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

// Paint n houses with 3 colors, adjacent houses different colors
public int minCost(int[][] costs) {
    int r = costs[0][0], g = costs[0][1], b = costs[0][2];
    for (int i = 1; i < costs.length; i++) {
        int nr = costs[i][0] + Math.min(g, b);
        int ng = costs[i][1] + Math.min(r, b);
        int nb = costs[i][2] + Math.min(r, g);
        r = nr; g = ng; b = nb;
    }
    return Math.min(r, Math.min(g, b));
}

Identify states → Write transitions → Code dp update

for each position i:
    for each state s:
        dp[i][s] = max over all ways to reach state s at position i