动态规划——多状态动态规划问题

一、打家劫舍

二、打家劫舍 II

三、删除并获得点数

四、粉刷房子

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

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

七、买卖股票的最佳时机III

八、买卖股票的最佳时机IV

一、打家劫舍

打家劫舍

第一步：确定状态表示

当我们每次偷到第i间房子时，我们存在两种状态，即可以选择偷或者不偷该房子的金额。所以我们需要有两张dp表。

f[ i ] 表示偷到第 i 间房子时，小偷选择偷第 i 间房子的金额时，偷窃到的总金额最大。g[ i ]表示偷到第 i 间房子时，小偷选择不偷第 i 间房子的金额时，偷窃到的总金额最大。

第二步：推出状态转移方程

第三步：初始化dp表

我们在使用状态转移方程时，会用到 i-1位置的值，那么如果 i 为0的话，就会有越界访问的问题，所以我们需要初始化，f[0] = nums[0]，g[i] = 0。

填表顺序：因为在填写 i 位置的值时，我们要用到 i-1位置的值，所以需要从左往右依次填写。

最后的返回值：我们要返回光顾完所有房子后，所能偷到的最大金额，所以需要返回f[n-1] 和 g[i-1]两者的最大值。

解题代码：

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

二、打家劫舍 II

打家劫舍II

打家劫舍II和打家劫舍问题唯一不同的是，这道题的房子是围成一个圈的。我们可以将它转换成打家劫舍问题去处理。

其他方法就和打家劫舍问题一样了。

返回值就是上面两种情况的最大值。

解题代码：

class Solution 
{
public:int rob(vector<int>& nums) {int n = nums.size();return max(nums[0] + rob1(nums, 2, n-2), rob1(nums, 1, n-1));}int rob1(vector<int>& nums, int left, int right){int n = nums.size();if(left > right)return 0;vector<int> f(n);vector<int> g(n);f[left] = nums[left]; // 区间的起始位置是leftfor(int i = left; i <= right; i++){f[i] = g[i-1] + nums[i];g[i] = max(g[i-1], f[i-1]);}return max(g[right], f[right]); // 区间的最右是right}
};

三、删除并获得点数

删除并获得点数

预处理：我们需要注意题目说明中的这一句：选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

也就是说，你在拿到nums[i]的点数后，就不能选择它前一个和后一个元素了。比如，nums[i]为5，拿到5这个点数后，你就不能再拿3和4了。这个要求是不是又和打家劫舍很像了。所以我们最终还是将这个问题转换成了打家劫舍问题。

比如对于示例2：

解题代码：

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

四、粉刷房子

粉刷房子

第一步：确定状态表示

红：0，蓝：1，绿：2。

dp[i][j]：表示刷到第i个房子时，将其涂成第j种颜色时的最小花费。

第二步：推出状态转移方程

第三步：初始化dp表

在使用dp表时，要使用i-1，所以 i == 0时，就会发生越界访问的问题。所以初始化，

dp[0][0] = costs[0][0]，dp[0][1] = costs[0][1]，dp[0][2] = costs[0][2]。

填表顺序：从上向下，从左到右

最后的返回值是最后一行的最大值。

解题代码：

class Solution 
{
public:int minCost(vector<vector<int>>& costs) {int m = costs.size(), n = costs[0].size();// 红：0，蓝：1，绿：2// dp[i][j]:表示刷到第i个房子时，将其涂成第j种颜色时的最小花费vector<vector<int>> dp(m, vector<int>(3));dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2];for(int i = 1; i < m; i++){dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0];dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1];dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2];}return min(dp[m-1][0], min(dp[m-1][1], dp[m-1][2]));}
};

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

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

第一步：确定状态表示

根据题意和示例，大的状态表示就是在第i天结束后，所获得的最大利润，而对于第i天来说，我们又有三种可能的状态：卖出，买入，冷冻期。

卖出状态：0，买入状态：1，冷冻期：2

所以说，dp[i][j]：表示第 i 天结束后，处于第 j 种状态时，所获的最大利润。

dp[i][0] 表示：第 i 天结束之后，处于卖出状态，此时的最大利润。

dp[i][1] 表示：第 i 天结束之后，处于买入状态，此时的最大利润。

dp[i][2] 表示：第 i 天结束之后，处于冷冻期状态，此时的最大利润。

第二步：推出状态转移方程

对于上面的核心图，我们对卖出状态进行举例解释一下：

如果在第 i 天结束后处于卖出状态，需要看 i - 1 天是什么状态然后怎么做能够满足第 i 天结束处于卖出状态。

如果第 i - 1 天结束处于卖出状态，那第 i 天什么也不干，依旧处于卖出状态。

如果第 i - 1 天结束处于冷冻期，也就是说第 i 天不能进行任何操作，无法购买股票，当第 i 天结束后，就会结束冷冻期，进入卖出状态。

第三步：初始化dp表，dp[0][1] = -prices[0]。

从左往右，从上向下依次填表，最后返回最后一天的三种状态中的最大值。

解题代码：

class Solution 
{
public:int maxProfit(vector<int>& prices) {int m = prices.size();vector<vector<int>> dp(m, vector<int>(3));dp[0][1] = -prices[0];// 卖：0，买：1，冷冻：2for(int i = 1; i < m; i++){dp[i][0] = max(dp[i-1][0], dp[i-1][2]);dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);dp[i][2] = dp[i-1][1]+prices[i];}return max(max(dp[m-1][0], dp[m-1][1]), dp[m-1][2]);}
};

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

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

第一步：确定状态表示

根据题意，每一天都可能存在两种状态，买入状态和卖出状态。

所以，f[i]：表示第 i 天结束后，处于买入状态时，所获的最大利润。g[i]：表示第 i 天结束后，处于卖出状态时，所获的最大利润。

需要注意的是，每次卖出股票，需要支付手续费。

第二步：推出状态转移方程

第三步：初始化dp表，f[0] = -prices[0]。

填表顺序为从左往右依次填写，g[i]和f[i]一起填写。最后的返回值是f[m-1]和f[m-1]中的最大值。

解题代码：

class Solution 
{
public:int maxProfit(vector<int>& prices, int fee) {int m =prices.size();vector<int> f(m);vector<int> g(m);f[0] = -prices[0];for(int i = 1; i < m; 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 max(f[m-1], g[m-1]);}
};

七、买卖股票的最佳时机III

买卖股票的最佳时机III

第一步：确定状态表示

首先，仍然是 dp[i] 表示第 i 天结束后所获得的最大利润。每一天有两种状态，卖出和买入状态。

而这道题和之前的题目不同的就是，它有交易次数的限制，只能够完成两笔交易。所以对于每一天来说，在卖出和买入状态之下，还有一种状态，那就是一直到第 i 天的交易次数。

所以，dp[i][j] ：表示第 i 天结束后，完成了 j 次交易后，所获得的最大利润。0表示完成了0次交易，1表示完成了1次交易，2表示完成了2次交易。

f[i][j] ：表示第 i 天结束后，处于买入状态时，完成了 j 次交易后，所获得的最大利润。

g[i][j] ：表示第 i 天结束后，处于卖出状态时，完成了 j 次交易后，所获得的最大利润。

第二步：推出状态转移方程

第三步：初始化dp表

填表顺序为从左往右，从上往下依次填写，g[i]和f[i]一起填写。

解题代码：

class Solution 
{const int n = -0x3f3f3f3f;
public:int maxProfit(vector<int>& prices) {int m = prices.size();vector<vector<int>> f(m, vector<int>(3, n)); // 买入vector<vector<int>> g(m, vector<int>(3, n)); // 卖出f[0][0] = -prices[0], g[0][0] = 0;for(int i = 1; i < m; i++){for(int j = 0; j < 3; j++){f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);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]);}}int ret = 0;for(int i = 0; i < 3; i++){if(g[m-1][i] > ret)ret = g[m-1][i];}return ret;}
};

八、买卖股票的最佳时机IV

买卖股票的最佳时机IV

这一道题的思路，和买卖股票的最佳时机III一模一样，只是把最多交易次数限定成了一个未知数。我们所有的解题方法都与他相同。

解题代码：

class Solution 
{const int n = -0x3f3f3f3f;
public:int maxProfit(int k, vector<int>& prices) {int m = prices.size();vector<vector<int>> f(m, vector<int>(k+1, n)); // 买入vector<vector<int>> g(m, vector<int>(k+1, n)); // 卖出f[0][0] = -prices[0], g[0][0] = 0;for(int i = 1; i < m; i++){for(int j = 0; j <= k; j++){f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);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]);}}int ret = 0;for(int i = 0; i <= k; i++){if(g[m-1][i] > ret)ret = g[m-1][i];}return ret;}
};