动态规划——多状态动态规划问题
目录
一、打家劫舍
第一步：确定状态表示
当我们每次偷到第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和打家劫舍问题唯一不同的是，这道题的房子是围成一个圈的。我们可以将它转换成打家劫舍问题去处理。
其他方法就和打家劫舍问题一样了。
返回值就是上面两种情况的最大值。
解题代码：
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]; // 区间的起始位置是left
for(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，冷冻：2
for(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
第一步：确定状态表示
首先，仍然是 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
这一道题的思路，和买卖股票的最佳时机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;
}
}; 
原文地址：https://blog.csdn.net/zdlynj/article/details/142392350
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！