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

*注：实际开发中可使用虚拟节点简化初始化逻辑，避免单独处理 n=0 或索引越界的情况。

2. 打家劫舍 II (House Robber 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];
        
        // 情况 1：偷第一家，不偷最后一家 [0, n-2]
        int res1 = robRange(nums, 0, n - 2);
        // 情况 2：不偷第一家，可偷最后一家 [1, n-1]
        int res2 = robRange(nums, 1, n - 1);
        
        return max(res1, res2);
    }

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];
        g[start] = 0;
        
        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. 删除并获得点数 (Delete and Earn)

题目描述： 你可以选择任意数字 x，获得 x * count(x) 的分数，但必须删除所有 x-1 和 x+1。

思路分析： 这本质上是一个打家劫舍问题的变体。如果我们选择了数值 x，就不能选择 x-1 和 x+1。我们可以先统计每个数值的总和，构建一个新的数组，然后在这个新数组上应用打家劫舍的逻辑。

代码实现：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxVal = 0;
        for (int x : nums) maxVal = max(maxVal, x);
        
        vector<int> arr(maxVal + 1, 0);
        for (int x : nums) arr[x] += x;
        
        int n = arr.size();
        vector<int> f(n, 0);
        vector<int> g(n, 0);
        
        f[0] = arr[0];
        g[0] = 0;
        
        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        
        return max(f[n - 1], g[n - 1]);
    }
};

4. 粉刷房子 (Paint House)

题目描述： 有 n 栋房子，每栋房子可以用 k 种颜色粉刷，不同颜色的成本不同。要求相邻房子颜色不同，求最小成本。

思路分析： 这是一个二维 DP 问题。状态不仅包含房子下标 i，还包含当前选择的颜色 j。

• dp[i][j]：粉刷到第 i 栋房子且使用颜色 j 的最小花费。
• 转移时，需从上一栋房子的其他颜色中选择最小值。

代码实现：

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        
        // dp[i][j] 表示第 i 天刷第 j 种颜色的最小花费
        vector<vector<int>> dp(n, vector<int>(3));
        
        // 初始化第一天
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
        }
        
        return min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
    }
};

股票买卖系列

股票问题是多状态 DP 的经典应用场景，通常涉及买入、卖出、冷冻期、手续费等约束。

1. 含冷冻期 (Best Time to Buy and Sell Stock with Cooldown)

状态定义：

• dp[i][0]：第 i 天持有股票的最大利润。
• dp[i][1]：第 i 天不持有股票，处于冷冻期的最大利润。
• dp[i][2]：第 i 天不持有股票，不处于冷冻期的最大利润。

转移方程：

• dp[i][0] = max(dp[i-1][0], dp[i-1][2] - price[i]) （保持持有 或 从非冷冻期买入）
• dp[i][1] = dp[i-1][0] + price[i] （今天卖出，进入冷冻期）
• dp[i][2] = max(dp[i-1][1], dp[i-1][2]) （保持非冷冻期 或 从冷冻期恢复）

代码实现：

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][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
        }
        
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

2. 含手续费 (Best Time to Buy and Sell Stock with Transaction Fee)

思路： 每次交易收取固定费用 fee。可以在买入或卖出时扣除，这里选择在卖出时扣除。

状态定义：

• f[i]：第 i 天持有股票的最大利润。
• g[i]：第 i 天不持有股票的最大利润。

转移方程：

• f[i] = max(f[i-1], g[i-1] - price[i])
• g[i] = max(g[i-1], f[i-1] + price[i] - fee)

代码实现：

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. 最多两笔交易 (Best Time to Buy and Sell Stock III)

思路： 限制交易次数为 2 次。需要增加一个维度记录交易次数。

状态定义：

• f[i][j]：第 i 天完成 j 次交易后，处于持有状态的最大利润。
• g[i][j]：第 i 天完成 j 次交易后，处于不持有状态的最大利润。

注意： 交易次数 j 在卖出时增加。初始化为负无穷以表示非法状态。

代码实现：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        
        const int INF = 0x3F3F3F3F;
        vector<vector<int>> f(n + 1, vector<int>(3, -INF));
        vector<vector<int>> g(n + 1, vector<int>(3, -INF));
        
        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 = 0;
        for (int j = 0; j <= 2; j++) {
            res = max(res, g[n][j]);
        }
        return res;
    }
};

4. 最多 k 笔交易 (Best Time to Buy and Sell Stock IV)

思路： 这是第三题的通用版本，只需将交易次数限制从 2 改为 k。

代码实现：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0 || k == 0) return 0;
        
        const int INF = 0x3F3F3F3F;
        vector<vector<int>> f(n + 1, vector<int>(k + 1, -INF));
        vector<vector<int>> g(n + 1, vector<int>(k + 1, -INF));
        
        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 = 0;
        for (int j = 0; j <= k; j++) {
            res = max(res, g[n][j]);
        }
        return res;
    }
};

总结

通过以上案例，我们可以总结出多状态 DP 的核心要点：

1. 状态拆分：当单一状态无法表达决策结果时（如选/不选、买/卖），引入多维数组或并行数组。
2. 互斥关系：如打家劫舍中相邻不可选，股票中买入前需卖出，明确状态间的依赖与互斥。
3. 边界处理：注意初始化（如负无穷表示不可达）、数组越界及空输入情况。
4. 降维优化：当状态过多时，可尝试将部分状态分离成独立数组，降低空间复杂度或提升可读性。

掌握这些模式后，面对复杂的 DP 问题，关键在于准确拆解状态，理清转移逻辑。