状态机 DP

int maxProfit(int[] prices) {
    int hold = -prices[0], cash = 0;
    for (int i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i]); // 卖出
        hold = Math.max(hold, -prices[i]);       // 买入
    }
    return cash;
}

int maxProfit(int[] prices) {
    int hold = -prices[0], cash = 0;
    for (int i = 1; i < prices.length; i++) {
        int newCash = Math.max(cash, hold + prices[i]);
        int newHold = Math.max(hold, cash - prices[i]);
        cash = newCash;
        hold = newHold;
    }
    return cash;
}

int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) return greedyProfit(prices); // 退化为无限次

    int[][] hold = new int[n][k + 1];
    int[][] cash = new int[n][k + 1];
    for (int j = 0; j <= k; j++) hold[0][j] = -prices[0];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            cash[i][j] = Math.max(cash[i-1][j], hold[i-1][j] + prices[i]);
            hold[i][j] = Math.max(hold[i-1][j], cash[i-1][j-1] - prices[i]);
        }
    }
    return cash[n-1][k];
}

int maxProfit(int[] prices) {
    int hold = -prices[0], frozen = 0, free = 0;
    for (int i = 1; i < prices.length; i++) {
        int newHold = Math.max(hold, free - prices[i]);
        int newFrozen = hold + prices[i]; // 卖出 → 进入冷冻
        int newFree = Math.max(free, frozen); // 冷冻结束
        hold = newHold; frozen = newFrozen; free = newFree;
    }
    return Math.max(frozen, free);
}

// dp[i][state] = 第 i 阶段处于 state 的最优值
for (int i = 1; i <= n; i++) {
    for (int s = 0; s < NUM_STATES; s++) {
        dp[i][s] = -INF;
        for (int prev : transitions[s]) { // 哪些状态能转移到 s
            dp[i][s] = Math.max(dp[i][s], dp[i-1][prev] + gain[i][s]);
        }
    }
}

// 状态：0=不偷当前，1=偷当前
int rob(int[] nums) {
    int notRob = 0, rob = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int newRob = notRob + nums[i];
        int newNotRob = Math.max(notRob, rob);
        rob = newRob; notRob = newNotRob;
    }
    return Math.max(rob, notRob);
}