Day44 | 动态规划 ：状态机DP 买卖股票的最佳时机IV&&买卖股票的最佳时机III&&309.买卖股票的最佳时机含冷冻期

动态规划应该如何学习？-CSDN博客

本次题解参考自灵神的做法，大家也多多支持灵神的题解

买卖股票的最佳时机【基础算法精讲 21】_哔哩哔哩_bilibili

希望读者在阅读之前先看完这篇博客

Day43 | 动态规划 ：状态机DP 买卖股票的最佳时机&&买卖股票的最佳时机II-CSDN博客

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

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,vector<int>& prices)

2.终止条件

就是在前两题的基础上了一个不合法的状态，那就是交易次数小于0的话要返回负无穷

注意判断的顺序，交易次数j一定要先判断，因为只要j小于0那肯定是不合法的

		if(j<0)return INT_MIN;if(i<0)if(status==1) return INT_MIN;elsereturn 0;

3.本层逻辑

在我们加prices[i]的时候，就说明是卖出股票，就说明第i天进行了一次交易，第i天的利润是prices[i]，那前i-1天的利润就是在最多交易j-1笔的情况下的最大利润，传入j-1

		if(status==1)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,vector<int>& prices){if(j<0)return INT_MIN;if(i<0)if(status==1) return INT_MIN;elsereturn 0;if(status==1)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,vector<int>& 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,vector<int>& prices,vector<vector<vector<int>>>& dp){if(j<0)return INT_MIN;if(i<0)if(status==1) return INT_MIN;elsereturn 0;if(dp[i][j][status]!=-1)return dp[i][j][status];if(status==1)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,vector<int>& prices) {vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(k+1,vector<int>(2,-1)));return dfs(prices.size()-1,k,0,prices,dp);}
}; 

//lambda
class Solution {
public:int maxProfit(int k,vector<int>& prices) {vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(k+1,vector<int>(2,-1)));function<int(int,int,int)> dfs=[&](int i,int j,int status)->int{if(j<0)return INT_MIN;if(i<0)if(status==1) return INT_MIN;elsereturn 0;if(dp[i][j][status]!=-1)return dp[i][j][status];if(status==1)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[i+1][j][0]=max(dp[i][j][0],dp[i][j-1][1]+prices[i]);
dp[i+1][j][1]=max(dp[i][j][1],dp[i][j][0]-prices[i]);

3.dp数组如何初始化(难理解的点)

1.第一维度prices.size()+1是我们的数组下标表示天数的i从1开始

2.表示交易次数的j初始化是k+2的大小是因为

-1,0,1,2，…，k一共是k+2个状态，这一点和递归里面的对应

3.对应递归的终止条件，j必须大于0才是合法的，其他的都是不合法的，所以一开始初始化都是负无穷(除以2是为了防止溢出)

然后单独把j大于0，并且是第0天（对应i<0的if），也不持有股票(对应的是递归里的if（status==0)）都赋值为0，表示这种情况下没有利润

vector<vector<vector<int>>> dp(prices.size()+1,vector<vector<int>>(k+2,vector<int>(2,INT_MIN/2)));
for(int i=1;i<=k+1;i++)dp[0][i][0]=0;

4.确定遍历顺序

后续结果需要依赖前面的计算结果，故使用从前往后遍历

		for(int i=0;i<prices.size();i++){for(int j=1;j<=k+1;j++){dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-1][1]+prices[i]);dp[i+1][j][1]=max(dp[i][j][1],dp[i][j][0]-prices[i]);}}

完整代码

class Solution {
public:int maxProfit(int k,vector<int>& prices) {vector<vector<vector<int>>> dp(prices.size()+1,vector<vector<int>>(k+2,vector<int>(2,INT_MIN/2)));for(int i=1;i<=k+1;i++)dp[0][i][0]=0;for(int i=0;i<prices.size();i++){for(int j=1;j<=k+1;j++){dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-1][1]+prices[i]);dp[i+1][j][1]=max(dp[i][j][1],dp[i][j][0]-prices[i]);}}return dp[prices.size()][k+1][0];}
}; 

4.滚动数组优化

和01背包一样，前面都是i后面都是i-1

由于j要靠j-1推出来，所以需要从后往前遍历j

class Solution {
public:int maxProfit(int k,vector<int>& prices) {vector<vector<int>> dp(k+2,vector<int>(2,INT_MIN/2));for(int i=1;i<=k+1;i++)dp[i][0]=0;for(int i=0;i<prices.size();i++){for(int j=k+1;j>=1;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[k+1][0];}
}; 

123.买卖股票的最佳时机III

[123. 买卖股票的最佳时机 III - 力扣（LeetCode）](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/)

就是上一题k=2的情况，带进去就完了，直接结束

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

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

这题笔者还不够理解，后续再刷的时候再次回顾

思路：

在 122. 买卖股票的最佳时机 II 的基础上，只需修改一处：在计算持有股票的状态时，把 dfs(i−1,0) 改成 dfs(i−2,0)。道理和 198. 打家劫舍 是一样的，因为第 i 天买股票的话第 i−1 天不能卖，只能从第 i−2 天没有股票的状态转移过来。注意 dfs(i−2,0) 并不意味着第 i−2 天一定卖了股票，而是在没有股票下的最优状态。

请注意，这会导致边界条件多了一个 dfs(−2,0)=0

请注意，dfs(−2,1) 是访问不到的，所以下面翻译成递推时，无需初始化这个状态（不需要写 f[0][1]=−∞）。

1.回溯法

class Solution {
public:int dfs(int i,int status,vector<int>& prices){if(i<0)if(status==1)return INT_MIN;elsereturn 0;if(status==1)return max(dfs(i-1,1,prices),dfs(i-2,0,prices)-prices[i]);elsereturn max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);}int maxProfit(vector<int>& prices) {return dfs(prices.size()-1,0,prices);}
};

2.记忆化搜索

class Solution {
public:int dfs(int i,int status,vector<int>& prices,vector<vector<int>>& dp){if(i<0)if(status==1)return INT_MIN;elsereturn 0;if(dp[i][status]!=-1)return dp[i][status];if(status==1)return dp[i][status]=max(dfs(i-1,1,prices,dp),dfs(i-2,0,prices,dp)-prices[i]);elsereturn dp[i][status]=max(dfs(i-1,0,prices,dp),dfs(i-1,1,prices,dp)+prices[i]);}int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,-1));return dfs(prices.size()-1,0,prices,dp);}
};

3.动态规划

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size()+2,vector<int>(2,0));dp[0][1]=INT_MIN/2;dp[1][1]=INT_MIN/2;for(int i=0;i<prices.size();i++){dp[i+2][1]=max(dp[i+1][1],dp[i][0]-prices[i]);dp[i+2][0]=max(dp[i+1][0],dp[i+1][1]+prices[i]);}return dp[prices.size()+1][0];}
};