C/C++ 动态规划实战：从打家劫舍到股票买卖的多状态 DP 解析

为了简化边界处理，也可以使用虚拟节点（多开一位空间）：

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

打家劫舍 II

题目描述

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

分析

环形结构打破了线性 DP 的连续性。解决思路是将环拆成两条线：

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

删除并获得点数

题目描述

每次选择一个数字获得对应点数，但必须删除该数字的所有相邻值（x-1 和 x+1）。

分析

这题本质是打家劫舍的变种。如果选择了数值 x，就不能选择 x-1 和 x+1。我们可以先统计每个数值的总和（例如出现多次的 x 累加），然后将其转化为'不能选择相邻索引'的问题。

1. 构建新数组 arr，arr[x] 存储所有值为 x 的数字之和。
2. 在 arr 上运行标准的打家劫舍逻辑。

代码实现

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10010;
        vector<int> arr(N, 0);
        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]);
    }
};

粉刷房子

题目描述

有 n 栋房子，每栋房子可以刷红、绿、蓝三种颜色，相邻房子颜色不能相同，求最小花费。

分析

这是二维 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]：持有股票（买入状态）
2. dp[i][1]：不持有股票，且不在冷冻期（可交易状态）
3. dp[i][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][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]);
    }
};

买卖股票的最佳时机含手续费

题目描述

无限次交易，但每次交易需支付固定手续费。

分析

简化为两个状态：持有 (f) 和 不持有 (g)。

• f[i] = max(f[i-1], g[i-1] - price)
• g[i] = max(g[i-1], f[i-1] + price - 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];
    }
};

买卖股票的最佳时机 III & IV

题目描述

• III：最多完成两笔交易。
• IV：最多完成 k 笔交易。

分析

当交易次数有限制时，状态需要增加一维表示已完成的交易次数。为了避免三维数组的复杂性，通常将'买入'和'卖出'状态拆分为两个二维数组 f[k] 和 g[k]。

• f[i][j]：第 i 天，完成了 j 次交易，处于买入状态的最大利润。
• g[i][j]：第 i 天，完成了 j 次交易，处于卖出状态的最大利润。

注意初始化的细节，特别是 j=0 时的买入状态应设为负无穷，表示不可能发生。

代码实现 (通用 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. 互斥状态：如打家劫舍中的选与不选，粉刷房子中的不同颜色，通常用多个数组或二维 DP 列表示。
2. 时间维度：股票问题引入了天数作为外层循环，内层根据状态转移。
3. 状态拆分技巧：当状态超过三维难以管理时（如股票交易的买入/卖出/次数），可以将互斥动作（买/卖）拆分为两个二维表，降低维度复杂度。
4. 边界处理：初始化时要特别注意非法状态（如未开始交易却持有股票）应设为极小值，避免干扰最大值计算。

掌握这些模式后，面对复杂的 DP 题目，只需理清状态定义和转移关系，即可逐步构建解决方案。