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

打家劫舍 II

题目

本题主要和上一题不同的是，收尾相连了，那么就进行特殊处理下第一个位置。 在上一题的基础上处理第一个位置：将一个线性的数组根据题意（第一个位置选 / 不选的情况）分成两份。

1. 第一个位置选的时候就代表数组下标 1 和 n-1 两处是不选的，再从 2 ~ 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(nums[0] + robRange(2, n - 2, nums), robRange(1, n - 1, nums));
    }
    
    int robRange(int l, int r, vector<int>& nums) {
        if (l > r) return 0;
        int n = nums.size(); 
        vector<int> f(n);
        vector<int> g(n);
        f[l] = nums[l];
        for (int i = l + 1; i <= r; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        return max(f[r], g[r]);
    }
};

删除并获得点数

题目

当选择 5 后就会删除其 5-1=4 和 5+1=6 的数。

分析题目

本题可以通过新增一个数组，将出现的情况都存到这些数组中，然后在这个数组中进行一个打家劫舍问题的分析，最终就得到了答案。

题解核心逻辑

class Solution {
public:
    const static int N = 10010;
    int arr[N] = {};
    int f[N] = {}, g[N] = {};
    
    int deleteAndEarn(vector<int>& nums) {
        int valmax = 0;
        for (auto x : nums) { 
            arr[x] += x; 
            valmax = max(valmax, x);
        }
        for (int i = 1; i <= valmax; i++) {
            f[i] = g[i-1] + arr[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        return max(f[valmax], g[valmax]);
    }
};

粉刷房子

题目

相邻房子的颜色不能相同，要求的是在上述条件下的最低花费成本。

题解核心逻辑

1. 状态表示：
   • dp[i][0]：分刷到 i 位置的时候，最后一个位置刷上了红色，此时的最小花费
   • dp[i][1]：蓝色
   • dp[i][2]：绿色
2. 状态转移方程：
   • 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][1], dp[i-1][0]) + costs[i-1][2]

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size(); 
        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][1], dp[i-1][0]) + costs[i-1][2];
        }
        return min(min(dp[n][0], dp[n][1]), dp[n][2]);
    }
};

中途总结

通过上面的几道题我们可以知道：当遇到类似打家劫舍的多状态 DP 时我们可以通过多个 DP 来保存他们各自的状态，并相互的使用 DP 来算出最终答案。

1. 按摩师中的多状态：预约和不预约两种状态
2. 打家劫舍 II 和删除并获得点数这两题的多状态：则是在简单的打家劫舍上进行了一定的改变（分别使用到了特殊处理和 Hash）
3. 而粉刷房子呢则是在前面都是两种互斥的状态下引入了三状态的情况，从而也就是进一步的对打家劫舍的多状态进行了提升，认识多状态不仅仅只是互斥的打家劫舍的两种状态，而是可以是不同的多种状态组成，通过分析多种状态相互的关系推出状态转移方程

下面就将继续多状态 DP 问题了，不再是打家劫舍而是股票问题，这类问题也就是经典的多状态问题。

买卖股票的最佳时机含冷冻期

题目

交易次数无限，但卖出后有冷冻期。

题解核心逻辑

1. 状态表示：
   • dp[i][0]：第 i 天结束之后，处于'买入'状态，此时的最大利润
   • dp[i][1]：第 i 天结束之后，处于'可交易'状态，此时的最大利润
   • dp[i][2]：第 i 天结束之后，处于'冷冻期'状态，此时的最大利润
2. 状态转移方程：
   • 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]

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]);
    }
};

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

题目

交易次数无限，但每次都有手续费。

题解核心逻辑

1. 状态表示：
   • f[i]：第 i 天结束之后，处于'买入'状态，此时的最大利润
   • g[i]：第 i 天结束之后，处于'卖出'状态，此时的最大利润
2. 状态转移方程：
   • f[i] = max(f[i-1], g[i-1] - prices[i])
   • g[i] = max(g[i-1], f[i-1] + prices[i] - fee)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size(); 
        vector<int> f(n);
        vector<int> g(n);
        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];
    }
};

买卖股票的最佳时机 III

题目

最多只能完成两笔交易。

题解核心逻辑

1. 状态表示：
   • f[i][j]：第 i 天结束之后，完成了 j 次交易，此时处于'买入'状态下的最大利润
   • g[i][j]：第 i 天结束之后，完成了 j 次交易，此时处于'卖出'状态下的最大利润
2. 状态转移方程：
   • f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i])
   • g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])

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(g[n][j], res);
        }
        return res;
    }
};

买卖股票的最佳时机 IV

本题本质和上一题几乎完全一样，只需将交易次数 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(g[n][j], res);
        }
        return res;
    }
};

最后总结

通过上述多状态问题包含打家劫舍和股票问题后，这里进行一定性的总结帮助大家复习和回顾。

1. 打家劫舍主要涉及到：互斥的多状态问题，也就是选择 or 不选择的问题，此处一般有两种状态，也是一种线性 DP。
2. 一般来说会分成两个数组来看，这是最基础的情况。
3. 而在到后续的《粉刷房子》这道题引出了多状态的影子，也就是通过不同颜色且相互互斥的情况衍生出多个 DP 进行分别表示。
4. 再到后续的股票问题（最大利润 + 天数 + 买入/卖出），分别不断的引入多种状态：冷冻期、手续费、最佳时机（限制次数）。
5. 其中最主要的在于先写出状态表示，如：f[i][j]：第 i 天结束之后，完成了 j 次交易，此时处于'买入'状态下的最大利润。
6. 当得出了状态表示后：进行分析状态得出状态转移方程，而状态分析也有技巧：通过将状态一一列出来进行分析，它们相互的关系。
7. 当我们发现我们写出来的状态表示中的状态超过了 3 种后，就可以通过将其中的一个状态单独出来将原本一个数组的截成两个数组，这分别体现在：打家劫舍（选择/不选择）、买卖股票（买入/卖出）。