专题二十_动态规划_简单多状态dp问题_买卖股票系列问题_算法专题详细总结
目录
动态规划
在完成了前面动态规划相关内容的铺垫之后，我们已经对斐波那契模型以及路径问题有了清晰的认识。在此基础上，接下来我们将步入一个全新的章节 —— 简单多状态 dp 问题。
1. 按摩师（easy）
解析：
就是简单的dp问题，那我们来一步步分析清楚就能很快的解答：
1.状态表达式：
经验+题目意思
dp[i]表示：以i结尾的位置的最大服务时间
2.状态转移方程
3.初始化
初始f[i] 和 g[i] ，f[0] 就是初始化0位置要选的结果，即f[0]=nums[0]
g[0] 就是不选，不用进行初始化
4.填表方向
每次只有把i-1位置填了才能填当前位置，所填表方向从左往右填
5.返回值：
返回两种状态下的最大值即可
代码编写：
class Solution {
public:
int massage(vector<int>& nums) {
int n=nums.size();
if(n==0) return 0;
vector<int> f(n+1);
vector<int> g(n+1);
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]);
}
};总结：
本题不是很难，主要就是要学会分析当前问题的情况，学会分类讨论，讨论出当前位置是选还是不选比较合适，从而分出两个函数来一个单独代表选的情况，一个单独代表不选
2. 打家劫舍II （medium）
解析：
1.状态表达式：
dp[i]表示：以i位置为结尾的最大利润
2.状态转移方程
仍然是设置f[i]表示当前位置选 跟 g[i]表示当前位置不选 两个表达式，这样就可以求出每一个位置选或者不选的不同的值，然后求出最后的最大值即可；
由于这一题是一个环形，所以就存在下面两种方案：
0位置选：0位置选了，1位置和n-1位置就不能被选了，那么这个数组的遍历范围就减小到[2,n-2]
0位置不选：那么1位置和n-1位置就有被选的资格，所以数组遍历范围就是[1,n-1];
那么为了多次创建数组，我们只需要封装一个函数rob1()每次传入数组的范围即可：
状态转移方程就是：
f[i]=g[i-1]+nums[i];
g[i]=max(g[i-1],f[i-1]);
3.初始化：
跟上一题一模一样的初始化，因为没有必要多开一个空间，又因为状态转移方程存在 n-1 所以每次只需要初始化传入的f[left]=nums[left] 然后从left+1开始遍历即可；
4.填表顺序：
依旧是从左往右填表
5.返回值
返回max(f[right],g[right]); 因为right位置是闭区间
代码编写：
class Solution {
public:
int n;
int rob(vector<int>& nums) {
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)
{
if(left>right) return 0;
vector<int> f(n);
auto g=f;
f[left]=nums[left];
for(int i=left+1;i<=right;i++)
{
f[i]=g[i-1]+nums[i];
g[i]=max(g[i-1],f[i-1]);
}
return max(f[right],g[right]);
}
};总结：
这一题值得好好反思总结跟上一题的区别，原理是一样的，但是细节问题很多好好对比一下还是收获满满的；
3. 删除并获得点数（medium）
题目意思很简单，就是每次选择一个数后比这个数大一和小的全部不能选，求出最大总和
解析：
我刚开始想构建一个完美的数组vector<pair<int,int>> hash；只存入nums里面的数字对应的总和，但是构建出来后，发现如果用上面的动态规划，那么就会跳过比如两个数字之间并不是相差1的大小，而是跳过了本来不应该跳过的数字，也就是说，就算那个数字不存在，也应该是0来表示
错误编写：
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<pair<int,int>> hash;
sort(nums.begin(),nums.end());
int n=nums.size();
for(int i=0;i<n;i++)
{
if(hash.size()==0)
{
hash.push_back({nums[i],nums[i]});
continue;
}
if(nums[i]>hash.back().first) hash.push_back({nums[i],nums[i]});
else hash.back().second+=nums[i];
}
for(auto e : hash) cout<<e.first<<" "<<e.second<<endl;
n=hash.size();
vector<int> f(n);
auto g=f;
f[0]=hash[0].second;
for(int i=1;i<n;i++)
{
f[i]=g[i-1]+hash[i].second;
g[i]=max(g[i-1],f[i-1]);
}
return max(f[n-1],g[n-1]);
}
};所以还是只能创建一个unordered_map<int,int> 来构建这个hash
1.状态表达式
通过上面的思路可以看出这一题就是前面的打家劫舍I问题，只需要把对应的数字求出对应的总和即可：
dp[i] 表示：以i位置为结尾的最大总和数
2.状态转移方程：
还是跟打家劫舍问题一样，设置两个数组，分别记录当前位置选还是不选的最终结果，然后分别取最大值
f[i]=g[i-1]+nums[i];
g[i]=max(g[i-1],f[i-1]);3.初始化：
任然是每次都要遍历i-1的位置，所以只需要初始化f[0]=hash[0],从1开始；
4.填表顺序：
从左往右
5.返回值
由于最后是[1,n]闭区间的位置，因为最后一个位置是hash里面最大值，所以开空间要开到ret的位置，也就是n+1个空间，最后返回max(f[n],g[n]);
代码编写：
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
unordered_map<int,int> hash;
int n=nums.size();
int ret=0;
for(int i=0;i<n;i++)
{
hash[nums[i]]+=nums[i];
ret=max(nums[i],ret);
}
n=ret;
vector<int> f(n+1);
auto g=f;
f[0]=hash[0];
for(int i=1;i<=n;i++)
{
f[i]=g[i-1]+hash[i];
g[i]=max(g[i-1],f[i-1]);
}
return max(f[n],g[n]);
}
};总结：
这一题很细节，就是要学会问题的转换，能够把题目意思转换成我们所熟悉的打家劫舍问题，我记得我第一次做的时候就是暴力求解，删掉了当前位置的前一个值和后一个值，然后求最大值
4. 粉刷房⼦（medium）
解析：
1.状态表达式
dp问题就是为了表达所有的情况，求出最优解，所以设置一维dp只能表示每一行的最优解，而不能表示选取每一个格子后是否为最优解
设置二维:
dp[i][0]:表示在第i个房子下，用0号颜色情况下的所有粉刷最小费用
dp[i][1]:表示在第i个房子下，用1号颜色情况下的所有粉刷最小费用
dp[i][2]:表示在第i个房子下，用2号颜色情况下的所有粉刷最小费用
2.状态转移方程：
由于只有三个颜色，那么完全可以单独为每一个dp[i][0/1/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][0],dp[i-1][1])+costs[i-1][2];
3.初始化：
多加一行，初始化为0 即可，就是为了避免越界
4.填表顺序：
从上往下，从左往右填表
5.返回值：
返回最后一行的最小值即可
代码编写：
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n=costs.size();
vector<vector<int>> dp(n+1,vector<int>(3));
int ret=INT_MAX;
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];
if(i==n) ret=min(min(dp[i][0],dp[i][1]),dp[i][2]);
}
return ret;
}
};总结：
这一题需要考虑的很细致，了解到怎么样才能将每一个房子的每一个颜色都考虑进来，很值得反复思考，让我更加深刻的理解到，动态规划是一个能够得到所有情况的最优解的办法
下面就是买卖股票类型，也是我当年的噩梦了：
5. 买卖股票的最佳时机含冷冻期（medium）
解析:
这一题买卖股票一共分为3个阶段，“买入”，“可交易”（手上没有股票，也不处于冷冻期），“冷冻期”
那么我们要考虑每一个阶段的dp，就要单独把每一个阶段单独拿出来进行考虑，给每一个阶段进行编号：
“买入” --> 0
“可交易” --> 1
“冷冻期” --> 2
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]-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
dp[i][2]=dp[i-1][0]+p[i];3.初始化：
我最开始式多开了一行，就是为了避免越界的问题：就让p[i-1]
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i-1]);
初始化多开的第一行为0，但是这里我没有考虑到第1行取最大值会取到0，本应该在dp[1][0] 的位置是应该只买入的时候，当前的状态应该是负值，但是变成了0，最后影响了结果
所以这题初始化很简单，不用多开，只需要考虑第一天的所有状态即可：
dp[0][0]表示第0天只买入，dp[0][0]=-p[0];
dp[0][1]表示第0天为可交易，dp[0][1]=0;
dp[0][2]表示第0天为冷冻期，就是当天买入，当天卖出，dp[0][0]=0；
所以只用初始化dp[0][0]=-p[0]即可；
4.填表顺序：
从左往右，从上往下，依次填3个状态的dp表
5.返回值，只用返回最后一天的最大利润即可；
代码编写：
class Solution {
public:
int maxProfit(vector<int>& p) {
int n=p.size();
int ret=0;
vector<vector<int>> dp(n+1,vector<int>(3));
dp[0][0]=-p[0];
for(int i=1;i<n;i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
dp[i][2]=dp[i-1][0]+p[i];
if(i==n-1) ret=max(max(dp[i][0],dp[i][1]),dp[i][2]);
}
return ret;
}
};总结：
这一题的状态机就能很好的表达出上面是多状态dp问题，多状态dp，就是要逐个分析每个状态会发生的每一种情况，才能得到最优解
6. 买卖股票的最佳时期含⼿续费（medium）
解析：
有了上一题的经验，这一题就太好解决了
1.状态表达式：
这一题只有两个状态：
买入 -- > 0
可交易 --> 1
dp[i][0]表示：第i天时进行买入的最大利润
dp[i][1]表示：第i天时处于可交易状态的最大利润
2.状态转移方程：
根据上面的两个状态，来画出状态机，根据状态机来一步步秒杀状态转移方程
从买入到买入状态，就是当天什么也不干；从买入到卖出状态，就是卖掉手上的股票+p[i]，这里我们规定，到卖出一只股票算是一个完整的操作，我们就要在这个时候交手续费-fee
从卖出到卖出状态，就是当天什么也不干；从卖出到买入状态，就是当天在买入一只股票-p[i]
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]-fee);3.初始化：
还是只用考虑dp[0][0]第0天的时候处于买入状态:dp[0][0]=-p[i];处于可交易状态时dp[0][1]=0;就是第0天不买也不卖
4.填表顺序：
从左往右，从上往下，依次填买入和可交易两个表
5.返回值：
返回最后一天的最大值
编写代码：
class Solution {
public:
int maxProfit(vector<int>& p, int fee) {
int n=p.size();
vector<vector<int>> dp(n,vector<int>(2));
dp[0][0]=-p[0];
for(int i=1;i<n;i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]-fee);
}
return max(dp[n-1][0],dp[n-1][1]);
}
};总结：
这类多状态dp问题只要画好状态机，就能迎刃而解，要耐心分析状态的每一种表示方式
7. 买卖股票的最佳时机III（hard）
解析：
1.状态表达式：
在分析dp状态的时候，考虑到每一个格子都有多种状态，当天可能会存在“买入” 和 “卖出”两种状态，在对每一种状态进行单独分析：
“买入” --> f[i][j]表示：第i天结束之后，完成了j次交易，此时处于“买入”状态下的，最大利润
“卖出” --> g[i][j]表示：第i天结束之后，完成了j次交易，此时处于“卖出”状态下的最大利润
这里就把每一种状态的每一天完成了几次交易分析的很透彻
2.状态转移方程：
首先就是画出状态机，然后再一步步分析每种状态的多种表示方式
这里初始化就一起顺带放在里面，为了避免初始化越界的问题把g[i][j]单独来出来考虑，当j-1>=0的时候再将g[i][j]进行比较取最大值
g[i][j] = g[i - 1][j];if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
4. 填表顺序：
从「上往下填」每⼀⾏，每⼀⾏「从左往右」，两个表「⼀起填」。
代码编写：
class Solution {
public:
int maxProfit(vector<int>& p) {
int n=p.size();
vector<vector<int>> f(n,vector<int>(3,-0x3f3f3f));
auto g=f;
f[0][0]=-p[0],g[0][0]=0;
int ret=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]-p[i]);
g[i][j]=g[i-1][j];
if(j-1>=0) g[i][j]=max(g[i][j],f[i-1][j-1]+p[i]);
if(i==n-1) ret=max(g[i][j],ret);
}
}
return ret;
}
};总结：
这题很难，很细，还需要自己下去多总结，多思考~
8. 买卖股票的最佳时机IV（hard）
解析：
1.状态表达式：
在分析dp状态的时候，考虑到每一个格子都有多种状态，当天可能会存在“买入” 和 “卖出”两种状态，在对每一种状态进行单独分析：
“买入” --> f[i][j]表示：第i天结束之后，完成了j次交易，此时处于“买入”状态下的，最大利润
“卖出” --> g[i][j]表示：第i天结束之后，完成了j次交易，此时处于“卖出”状态下的最大利润
这里就把每一种状态的每一天完成了几次交易分析的很透彻
2.状态转移方程：
首先就是画出状态机，然后再一步步分析每种状态的多种表示方式
这里初始化就一起顺带放在里面，为了避免初始化越界的问题把g[i][j]单独来出来考虑，当j-1>=0的时候再将g[i][j]进行比较取最大值
g[i][j] = g[i - 1][j];if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
4. 填表顺序：
从「上往下填」每⼀⾏，每⼀⾏「从左往右」，两个表「⼀起填」。
代码编写：
class Solution {
public:
int maxProfit(int k, vector<int>& p) {
int n=p.size();
vector<vector<int>> f(n,vector<int>(k+1,-0x3f3f3f));
auto g=f;
f[0][0]=-p[0],g[0][0]=0;
int ret=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]-p[i]);
g[i][j]=g[i-1][j];
if(j-1>=0) g[i][j]=max(g[i][j],f[i-1][j-1]+p[i]);
if(i==n-1) ret=max(ret,g[i][j]);
}
}
return ret;
}
};总结：
这一题简直就是跟上一题思路一模一样，只需要改变一下j 的取值即可
总结不易~本节对我的收获很大，希望对你也是~！！！
原文地址：https://blog.csdn.net/2301_80636070/article/details/143810314
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！