C/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) {
        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。

分析： 这本质上也是打家劫舍的变种。如果我们选择了数值 i，就不能选择 i-1 和 i+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 栋房子，每栋房子可以用 k 种颜色粉刷，费用不同。相邻房子颜色不能相同，求最小花费。

分析： 这是多状态 DP 的典型应用。状态不仅包含下标，还包含当前选择的颜色。

• dp[i][j]：粉刷到第 i 栋房子，且第 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, 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 表或增加维度。
2. 状态互斥：如打家劫舍中的选/不选，粉刷房子中的颜色互斥。
3. 状态转化：如删除点数问题，通过预处理将复杂约束转化为标准模型。

接下来我们将进入更复杂的股票交易系列，涉及冷冻期、手续费及交易次数限制。

股票买卖系列

1. 含冷冻期

题目描述： 卖出股票后，第二天无法买入（冷冻期）。无限次交易。

分析： 需要维护三个状态：

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

状态转移：

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] - price[i]) （保持持有 或 从前一天可交易买入）
• dp[i][1] = max(dp[i-1][1], dp[i-1][2]) （保持空闲 或 从冷冻期解冻）
• dp[i][2] = dp[i-1][0] + price[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. 含手续费

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

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

• 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. 最多两笔交易 (III)

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

分析： 状态空间扩大。我们需要记录交易次数 k。

• 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 笔交易 (IV)

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

分析： 逻辑与 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;
    }
};

最终总结

通过以上 8 道由浅入深的多状态 DP 题目，我们可以归纳出解决此类问题的通用方法论：

1. 识别互斥性：打家劫舍类问题核心在于相邻互斥，通常拆分为'选/不选'两个状态。
2. 多维状态定义：当存在多种约束（如颜色、天数、交易次数）时，需在状态中显式体现。例如 dp[i][j] 中 j 代表交易次数或颜色索引。
3. 降维技巧：当状态超过三维难以维护时，可将'买入'和'卖出'状态拆分为两个二维数组，从而降低复杂度。
4. 状态机思维：股票问题本质是状态机的流转。明确每个状态的来源和去向，列出转移方程即可。
5. 边界处理：虚拟节点或负无穷初始化能有效避免越界和非法状态干扰。

掌握这些核心思路，面对复杂的多状态 DP 问题时，便能抽丝剥茧，找到最优解法。