C/C++ 算法入门：多状态动态规划——打家劫舍与股票买卖问题

2. 打家劫舍 II（环形数组）

题目描述： 房屋围成一圈，首尾相连。不能同时偷窃第一间和最后一间。

思路分析： 由于首尾互斥，我们可以将问题拆分为两种情况取最大值：

1. 偷第一家：则不能偷最后一家。范围是 [0, n-2]。
2. 不偷第一家：则可以偷最后一家。范围是 [1, n-1]。

注意处理边界情况，如数组长度为 1 时直接返回该值。

代码实现：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        
        // 情况 1：偷第一家，不偷最后一家 [0, n-2]
        int val1 = robRange(nums, 0, n - 2);
        // 情况 2：不偷第一家，可偷最后一家 [1, n-1]
        int val2 = robRange(nums, 1, n - 1);
        
        return max(val1, val2);
    }

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(f[i - 1], g[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 maxVal = 0;
        
        for (int x : nums) {
            arr[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] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        
        return max(f[maxVal], g[maxVal]);
    }
};

4. 粉刷房子

题目描述： 有 n 栋房子，每栋房子可以涂红、蓝、绿三种颜色之一，相邻房子颜色不能相同。求最小花费。

思路分析： 这是一个典型的三维状态简化问题。dp[i][j] 表示涂到第 i 栋房子且颜色为 j 的最小花费。由于相邻不能同色，状态转移时需要排除当前颜色。

代码实现：

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        // dp[i][j] 表示第 i 天刷第 j 种颜色的最小花费
        vector<vector<int>> dp(n + 1, vector<int>(3));
        
        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]：第 i 天结束后持有股票。
• dp[i][1]：第 i 天结束后不持有股票，且处于可交易状态。
• dp[i][2]：第 i 天结束后不持有股票，且处于冷冻期。

状态转移：

• 持有：前一天持有 或 前一天可交易今天买入。
• 可交易：前一天可交易 或 前一天冷冻期结束。
• 冷冻期：前一天持有今天卖出。

代码实现：

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. 含手续费

题目描述： 无限次交易，每次卖出收取固定手续费。

思路分析： 只需在卖出时减去手续费即可。状态简化为「持有」和「不持有」。

代码实现：

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）

题目描述： 最多完成两笔交易。

思路分析： 需要记录交易次数。为了避免三维数组，可以将「买入」和「卖出」状态分开成两个二维数组 f[k][j] 和 g[k][j]，分别表示完成 k 次交易后的买入/卖出状态利润。

代码实现：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // f[i][j]: 第 i 天，完成 j 次交易，处于买入状态
        // g[i][j]: 第 i 天，完成 j 次交易，处于卖出状态
        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) {
                    g[i][j] = max(g[i][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）

题目描述： 最多完成 k 笔交易。

思路分析： 逻辑与 III 完全一致，只是将交易次数上限从 2 改为 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) {
                    g[i][j] = max(g[i][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. 多维约束：如股票问题中的「天数 + 交易次数 + 持仓状态」，可通过拆分「买入表」和「卖出表」降低维度，避免直接使用三维数组带来的复杂度。
3. 状态转移：务必理清状态间的依赖关系，特别是边界条件（如第一天初始化、交易次数限制）的处理。

掌握这些模式后，面对复杂的 DP 问题，可以先尝试画出状态图，再推导转移方程，往往能事半功倍。