郑州 互联网 公司网站,西安短视频制作公司,关键词排名工具,网站域名设计方案Day44 | 动态规划 #xff1a;状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III309.买卖股票的最佳时机含冷冻期
动态规划应该如何学习#xff1f;-CSDN博客
本次题解参考自灵神的做法#xff0c;大家也多多支持灵神的题解
买卖股票的最佳时机【…Day44 | 动态规划 状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III309.买卖股票的最佳时机含冷冻期
动态规划应该如何学习-CSDN博客
本次题解参考自灵神的做法大家也多多支持灵神的题解
买卖股票的最佳时机【基础算法精讲 21】_哔哩哔哩_bilibili
希望读者在阅读之前先看完这篇博客
Day43 | 动态规划 状态机DP 买卖股票的最佳时机买卖股票的最佳时机II-CSDN博客
动态规划学习
1.思考回溯法深度优先遍历怎么写
注意要画树形结构图
2.转成记忆化搜索
看哪些地方是重复计算的怎么用记忆化搜索给顶替掉这些重复计算
3.把记忆化搜索翻译成动态规划
基本就是1:1转换 文章目录 Day44 | 动态规划 状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III309.买卖股票的最佳时机含冷冻期188.买卖股票的最佳时机IV思路分析子问题1.回溯 DFS2.记忆化搜索3.1:1翻译为动态规划4.滚动数组优化 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV
188. 买卖股票的最佳时机 IV - 力扣LeetCode
思路分析子问题
状态机的变化多了一个参数j表示我们最多可以交易几笔 在加减prices[i]的时候进行j-1表示我们进行了一笔交易那剩下在递归的时候最多只能交易j-1次
注意j-1只在加prices[i]或者减prices[i]的时候写一次加表示我们卖出可以看做一次交易减表示一次买进也可以看做一次交易但是加减prices[i]的时候都写就说明我们买进一次再卖出算成了两次交易这样就错了 笔者觉得在卖出的时候进行交易次数的计算比较好就使用这个
递归边界部分和前两道题不同的就是j如果小于0了那肯定就是不合法的状态因为我们的交易次数最少应该是0所以就返回一个负无穷表示这是不合法的
1.回溯 DFS
1.返回值和参数
i是每天的价格
status是状态表示是否持有股票
j是我们现在最多可以交易多少笔
dfs返回值是我们在前i天持有或者不持有股票在最多交易j次的前提下可以获得的最大利润
int dfs(int i,int j,int status,vectorint prices)2.终止条件
就是在前两题的基础上了一个不合法的状态那就是交易次数小于0的话要返回负无穷
注意判断的顺序交易次数j一定要先判断因为只要j小于0那肯定是不合法的 if(j0)return INT_MIN;if(i0)if(status1) return INT_MIN;elsereturn 0;3.本层逻辑
在我们加prices[i]的时候就说明是卖出股票就说明第i天进行了一次交易第i天的利润是prices[i]那前i-1天的利润就是在最多交易j-1笔的情况下的最大利润传入j-1 if(status1)return max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);elsereturn max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)prices[i]);完整代码
当然这是超时的
class Solution {
public:int dfs(int i,int j,int status,vectorint prices){if(j0)return INT_MIN;if(i0)if(status1) return INT_MIN;elsereturn 0;if(status1)return max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);elsereturn max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)prices[i]);}int maxProfit(int k,vectorint prices) {return dfs(prices.size()-1,k,0,prices);}
}; 2.记忆化搜索
就是搞一个哈希表dp全都初始化为-1每次返回前给哈希表dp赋值碰到不是-1的那就是算过的那就直接返回计算过的结果不需要再次递归了
class Solution {
public:int dfs(int i,int j,int status,vectorint prices,vectorvectorvectorint dp){if(j0)return INT_MIN;if(i0)if(status1) return INT_MIN;elsereturn 0;if(dp[i][j][status]!-1)return dp[i][j][status];if(status1)return dp[i][j][status]max(dfs(i-1,j,1,prices,dp),dfs(i-1,j,0,prices,dp)-prices[i]);elsereturn dp[i][j][status]max(dfs(i-1,j,0,prices,dp),dfs(i-1,j-1,1,prices,dp)prices[i]);}int maxProfit(int k,vectorint prices) {vectorvectorvectorint dp(prices.size(),vectorvectorint(k1,vectorint(2,-1)));return dfs(prices.size()-1,k,0,prices,dp);}
}; //lambda
class Solution {
public:int maxProfit(int k,vectorint prices) {vectorvectorvectorint dp(prices.size(),vectorvectorint(k1,vectorint(2,-1)));functionint(int,int,int) dfs[](int i,int j,int status)-int{if(j0)return INT_MIN;if(i0)if(status1) return INT_MIN;elsereturn 0;if(dp[i][j][status]!-1)return dp[i][j][status];if(status1)return dp[i][j][status]max(dfs(i-1,j,1),dfs(i-1,j,0)-prices[i]);elsereturn dp[i][j][status]max(dfs(i-1,j,0),dfs(i-1,j-1,1)prices[i]);};return dfs(prices.size()-1,k,0);}
}; 3.1:1翻译为动态规划
1.确定dp数组以及下标的含义 dfs换成dp就是数组以及下标含义
2.确定递推公式
dp[i1][j][0]max(dp[i][j][0],dp[i][j-1][1]prices[i]);
dp[i1][j][1]max(dp[i][j][1],dp[i][j][0]-prices[i]);3.dp数组如何初始化(难理解的点)
1.第一维度prices.size()1是我们的数组下标表示天数的i从1开始
2.表示交易次数的j初始化是k2的大小是因为
-1,0,1,2…k一共是k2个状态这一点和递归里面的对应
3.对应递归的终止条件j必须大于0才是合法的其他的都是不合法的所以一开始初始化都是负无穷(除以2是为了防止溢出)
然后单独把j大于0并且是第0天对应i0的if也不持有股票(对应的是递归里的ifstatus0)都赋值为0表示这种情况下没有利润
vectorvectorvectorint dp(prices.size()1,vectorvectorint(k2,vectorint(2,INT_MIN/2)));
for(int i1;ik1;i)dp[0][i][0]0;4.确定遍历顺序
后续结果需要依赖前面的计算结果故使用从前往后遍历 for(int i0;iprices.size();i){for(int j1;jk1;j){dp[i1][j][0]max(dp[i][j][0],dp[i][j-1][1]prices[i]);dp[i1][j][1]max(dp[i][j][1],dp[i][j][0]-prices[i]);}}完整代码
class Solution {
public:int maxProfit(int k,vectorint prices) {vectorvectorvectorint dp(prices.size()1,vectorvectorint(k2,vectorint(2,INT_MIN/2)));for(int i1;ik1;i)dp[0][i][0]0;for(int i0;iprices.size();i){for(int j1;jk1;j){dp[i1][j][0]max(dp[i][j][0],dp[i][j-1][1]prices[i]);dp[i1][j][1]max(dp[i][j][1],dp[i][j][0]-prices[i]);}}return dp[prices.size()][k1][0];}
}; 4.滚动数组优化
和01背包一样前面都是i后面都是i-1
由于j要靠j-1推出来所以需要从后往前遍历j
class Solution {
public:int maxProfit(int k,vectorint prices) {vectorvectorint dp(k2,vectorint(2,INT_MIN/2));for(int i1;ik1;i)dp[i][0]0;for(int i0;iprices.size();i){for(int jk1;j1;j--){dp[j][0]max(dp[j][0],dp[j-1][1]prices[i]);dp[j][1]max(dp[j][1],dp[j][0]-prices[i]);}}return dp[k1][0];}
}; 123.买卖股票的最佳时机III
[123. 买卖股票的最佳时机 III - 力扣LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/)
就是上一题k2的情况带进去就完了直接结束
