C++ 多状态 DP 思路：打家劫舍与股票买卖

2. 打家劫舍 II

房屋围成一圈，意味着首尾不能同时偷。把环形问题拆成两个线性情况：

1. 选第一个房子，不选最后一个（范围 0 ~ n-2）
2. 不选第一个房子，可选最后一个（范围 1 ~ n-1）

取两者的最大值就行。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

private:
    int robRange(const vector<int>& nums, int start, int end) {
        if (start > end) return 0;
        int n = nums.size();
        vector<int> f(n, 0);
        vector<int> g(n, 0);
        f[start] = nums[start];
        for (int i = start + 1; i <= end; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[end], g[end]);
    }
};

3. 删除并获得点数

选数字 x 拿 x 分，但必须删掉所有 x-1 和 x+1。这其实就是打家劫舍的变形：如果选了数值 x，就不能选 x-1 和 x+1。统计每个数值的总和，把值本身当成下标，问题就转化成了线性打家劫舍。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10010;
        int arr[N] = {};
        int valmax = 0;
        for (int x : nums) {
            arr[x] += x;
            valmax = max(valmax, x);
        }

        vector<int> f(valmax + 1, 0);
        vector<int> g(valmax + 1, 0);

        for (int i = 1; i <= valmax; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[valmax], g[valmax]);
    }
};

4. 粉刷房子

相邻房子颜色不能相同，求最小花费。用 dp[i][color] 表示第 i 个房子刷成某色时的最小总花费。因为相邻限制，当前颜色只能从前一个房子的其他颜色转移过来。

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(3, 0));

        for (int i = 1; i <= n; i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
        }
        return min({dp[n][0], dp[n][1], dp[n][2]});
    }
};

股票买卖系列

股票问题本质是状态机模型。根据是否持有、是否处于冷冻期等来定义状态。

1. 含冷冻期

卖出后第二天不能买入（冷冻期）。定义三个状态：

• dp[i][0]：持有股票
• dp[i][1]：不持有且可交易
• dp[i][2]：不持有且处于冷冻期

转移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - price)
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + price

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(3));

        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;

        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

2. 含手续费

每次交易收取固定手续费，在卖出时扣除。状态分为持有 f[i] 和不持有 g[i]。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n), g(n);
        f[0] = -prices[0];
        g[0] = 0;

        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        return g[n - 1];
    }
};

3. 最多两笔交易 (III)

需要记录交易次数 j。状态：第 i 天，已完成 j 次交易，当前持有/未持有。为避免三维数组，用 f[i][j] 表示持有，g[i][j] 表示未持有。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n + 1, vector<int>(3, -0x3F3F3F3F));
        vector<vector<int>> g(n + 1, vector<int>(3, -0x3F3F3F3F));
        g[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 2; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i - 1]);
                }
            }
        }

        int res = INT_MIN;
        for (int j = 0; j <= 2; j++) {
            res = max(res, g[n][j]);
        }
        return res;
    }
};

4. 最多 k 笔交易 (IV)

与 III 一样，把交易次数上限换成 k。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n + 1, vector<int>(k + 1, -0x3F3F3F3F));
        vector<vector<int>> g(n + 1, vector<int>(k + 1, -0x3F3F3F3F));
        g[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i - 1]);
                }
            }
        }

        int res = INT_MIN;
        for (int j = 0; j <= k; j++) {
            res = max(res, g[n][j]);
        }
        return res;
    }
};

多状态 DP 的关键是找准状态维度以及它们之间的转移关系。像打家劫舍那样简单互斥，可以用两个数组；颜色限制则增加颜色维度；股票问题则要根据买卖、冷冻等画状态机，再落地成方程。初始化和边界处理很容易出错，特别是像 III/IV 中负无穷的初始值，写的时候要小心。