动态规划入门：多状态 DP 问题解析（打家劫舍与股票买卖）

打家劫舍 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 start, int end, const vector<int>& nums) {
        if (start > end) return 0;
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        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]);
    }
};

删除并获得点数

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

题解核心逻辑

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxval = 0;
        vector<int> dp(20010, 0);
        for (auto v : nums) {
            dp[v] += v;
            maxval = max(maxval, v);
        }
        vector<int> f(maxval + 1);
        vector<int> g(maxval + 1);
        for (int i = 1; i <= maxval; i++) {
            f[i] = g[i - 1] + dp[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[maxval], g[maxval]);
    }
};

粉刷房子

对于题目给的二维数组的含义是：纵坐标代表房子的下标，横坐标代表颜色。其中注意的是相邻房子的颜色不能相同。要求的是在上述条件下的最低花费成本。

题解核心逻辑

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 问题了，不再是打家劫舍而是股票问题，这类问题也就是经典的多状态问题。

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

首先肯定是以 i 位置为结尾时的最大利润，但其中它可能会有多种状态，所以就还需要 3 行来表示状态：'买入'、'可交易'、'冷冻期'。

题解核心逻辑

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        // dp[i][0]：处于'买入'状态，此时的最大利润
        // dp[i][1]：处于'可交易'状态，此时的最大利润
        // dp[i][2]：处于'冷冻期'状态，此时的最大利润
        
        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]);
    }
};

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

交易次数无限，但每次都有手续费（买入和卖出只用出一次手续费）。若手里有股票就不能再买了。

题解核心逻辑

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

最多只能完成两笔交易。只能卖了股票，才能买新股票。

题解核心逻辑

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

本题本质和上一题几乎完全一样。

题解核心逻辑

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. 一般来说会分成两个数组来看，这是最基础的情况，当我们发现一个数组中它出现互斥的两种情况的时候就能一定的考虑到使用这种 DP。
3. 粉刷房子引出了多状态的影子，也就是通过不同颜色且相互互斥的情况衍生出多个 DP 进行分别表示。
4. 股票问题（最大利润 + 天数 + 买入/卖出），分别不断的引入多种状态：冷冻期、手续费、最佳时机（限制次数）。
5. 当得出了状态表示后：进行分析状态得出状态转移方程，通过将状态一一列出来进行分析，它们相互的关系。
6. 当我们发现我们写出来的状态表示中的状态超过了 3 种后，就可以通过将其中的一个状态单独出来将原本一个数组的截成两个数组。