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

2. 打家劫舍 II (LeetCode)

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

分析： 将环形问题拆解为线性问题。分两种情况讨论：

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(g[i - 1], f[i - 1]);
        }
        return max(f[end], g[end]);
    }
};

3. 删除并获得点数 (LeetCode)

题目描述： 选择数字 x 获得 x * count(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 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]);
    }
};

4. 粉刷房子 (LeetCode)

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

分析： 二维 DP。dp[i][j] 表示第 i 栋房子涂第 j 种颜色的最小花费。状态转移需排除同色。

代码实现：

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. 含冷冻期 (LeetCode)

状态定义：

• 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. 含手续费 (LeetCode)

分析： 每次交易收取固定费用。只需在卖出时减去 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. 最多两笔交易 (LeetCode III)

分析： 限制交易次数 k=2。状态需增加交易次数维度。为避免三维数组，将'买入'和'卖出'拆分为两个二维表 f[i][j] 和 g[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 次交易 (LeetCode IV)

分析： 将上述逻辑泛化，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. 多维约束：如股票问题中的天数、交易次数、持有状态，可通过降维技巧（拆分买入/卖出表）避免高维数组。
3. 状态转移：关键在于理清状态间的依赖关系，画出状态机图有助于理解。

掌握这些模式后，面对复杂的线性 DP 问题，便能快速定位状态定义并推导方程。