C/C++ 动态规划实战：多状态 DP 详解（打家劫舍与股票买卖）

为了简化边界判断，也可以使用虚拟节点（增加一位空间），这样循环可以从 1 开始直接遍历，无需单独处理 i=0。

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) {
        int n = nums.size();
        vector<int> f(n + 1, 0);
        vector<int> g(n + 1, 0);
        
        f[start + 1] = nums[start];
        for (int i = start + 1; i <= end; i++) {
            f[i + 1] = g[i] + nums[i];
            g[i + 1] = max(g[i], f[i]);
        }
        return max(f[end + 1], g[end + 1]);
    }
};

3. 删除并获得点数

题目特点：删除 x 会同时删除 x-1 和 x+1。

转化思路： 这本质上还是打家劫舍问题。如果选择了数值 x，就不能选 x-1 和 x+1。我们可以统计每个数字出现的总价值，构建一个新的数组，然后在这个新数组上运行打家劫舍逻辑。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 20010;
        vector<int> dp(N, 0);
        int maxVal = 0;
        
        for (int x : nums) {
            dp[x] += x;
            maxVal = max(maxVal, x);
        }
        
        vector<int> f(maxVal + 1, 0);
        vector<int> g(maxVal + 1, 0);
        
        for (int i = 1; i <= maxVal; i++) {
            f[i] = g[i - 1] + dp[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        
        return max(f[maxVal], g[maxVal]);
    }
};

4. 粉刷房子

题目特点：三种颜色，相邻房子颜色不同。

思路： 这是多状态 DP 的典型扩展。状态需要包含'房子下标'和'当前颜色'。

• dp[i][0]：第 i 个房子刷红色的最小花费。
• dp[i][1]：第 i 个房子刷绿色的最小花费。
• dp[i][2]：第 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][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        
        return min({dp[n][0], dp[n][1], dp[n][2]});
    }
};

股票买卖系列

股票问题是状态机 DP 的经典应用。我们需要明确每天结束时处于什么状态（持有、卖出、冷冻期等）。

1. 含冷冻期

状态定义：

• dp[i][0]：持有股票。
• dp[i][1]：不持有股票，且处于可交易状态（非冷冻期）。
• dp[i][2]：不持有股票，且处于冷冻期。

转移方程：

• 持有：要么前一天就持有，要么前一天可交易今天买入。
• 可交易：要么前一天就是可交易，要么前一天是冷冻期。
• 冷冻期：只能由前一天持有并卖出导致。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        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. 含手续费

区别：每次卖出时需扣除固定费用 fee。

调整：在卖出状态转移时减去 fee 即可。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n, 0); // 持有
        vector<int> g(n, 0); // 不持有
        
        f[0] = -prices[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. 最多两笔交易

难点：交易次数有限制，状态需增加'已完成交易次数'。

优化： 由于三维数组较难维护，可以将'买入'和'卖出'分开成两个二维数组 f[k][j] 和 g[k][j]，其中 k 代表交易次数，j 代表天数。或者直接使用一维滚动数组优化空间。

这里展示使用两个二维数组的思路，清晰表达状态分离：

• f[i][j]：第 i 天完成 j 次交易后处于买入状态。
• g[i][j]：第 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 笔交易

通用解法： 将上述代码中的 2 替换为 k 即可。逻辑完全一致，只是状态维度随 k 变化。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        
        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 的本质是将复杂约束拆解为互斥或递推的状态集合。

1. 打家劫舍类：核心是互斥选择，通常用两个数组分别表示'选'与'不选'，或通过拆分区间解决环形约束。
2. 粉刷房子类：引入颜色维度，本质是线性 DP 中增加了状态列，需注意相邻状态不可同色。
3. 股票买卖类：典型的有限状态机。关键是根据题目约束（冷冻期、手续费、交易次数）设计状态变量。当状态超过三维难以管理时，可将'买入/卖出'拆分为两个二维表，降低理解难度。

掌握这些模式后，面对变体题目只需微调状态定义与转移方程即可。