Day43 | 动态规划 ：状态机DP 买卖股票的最佳时机买卖股票的最佳时机II

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

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

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

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

动态规划学习：

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

注意要画树形结构图

2.转成记忆化搜索

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

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

基本就是1:1转换

121.买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

思路分析（子问题）：

最后一天发生了什么？

输入：[7,1,5,3,6,4]
输出：5

从低0天开始到第五天结束时的利润=从第0天开始到第四天结束时的利润+第五天的利润

第五天的利润有三种可能（就光说第五天这一天）

1.我啥也没干那就是0，因为我没有买进也没有卖出

2.我把我有的股票给卖了，那就是4，即prices[5]

3.我本来就没股票，我今天买入了，那就是-4，即-prices[5]

为什么是负的利润还要买？因为你卖的前提是你买了。

然后就是熟悉的往前推，从0到第四天结束的利润是前三天的利润+第四天的直到第0天

可以发现我们需要一个bool值来体现我们现在是否持有股票，false表示没有，true表示有

大家要注意理解：

我第i-1天的结束就是第i天的开始

重点：

dfs(i,status)的含义就是我从第0天到第i天，在status状态下所能得到的最大金额，status就是咱们提到的bool值0或1

如果我第i天持有股票，status==1，dfs（i，1）

那我第一个可能是我第i-1天就有股票但是我没卖掉，即i-1天的时候也有股票，那我在从0-i这几天的最大金额就肯定是dfs(i-1,1)

也有可能是我在第i天的时候买了，那说明我前面都没买也没卖，那前i-1天的总利润就是0，第i天的利润就是-prices[i]

dfs(i,1)=max(dfs(i-1,1),-prices[i])

如果我第i天没有股票，status==0，dfs（i，0）

那我第一个可能是我第i-1天就没有股票，然后今天也没买，那我在从0到i这几天的最大金额就肯定是dfs(i-1,0)

也有可能是我在0到i天中间买了股票了，一直没卖，到了今天才卖掉了，那我第i天的利润就是dfs(i-1,1)+prices[i]，因为你得保证你卖出的时候你的前一天是有股票的，不然卖啥啊对吧

（买的时候花的钱已经算到买的那天的利润里面去了，是负的）

dfs(i,0)=max(dfs(i-1,0),dfs(i-1,1)+prices[i])

最后返回的是什么，那肯定是最后一天不持有股票的情况，就是我们要的最大值了

这样的表示状态转移的图叫做状态机，从图中可以明显的看出状态的转移

大家把买入部分的dfs(i-1,0)当做0，就是本题的状态转移，正如上面所说，dfs(i-1,0)说的是我前一天没有股票的最大利润，这题里面我只要i-1天没有股票，那说明我前面都没买过股票，利润只能是0

结合灵神的图更好理解

1.回溯 DFS

1.返回值和参数

i是每天的价格

status是状态，表示是否持有股票

int dfs(int i,int status,vector<int>& prices)

2.终止条件

dfs(-1,0)表示前-1天不持有股票的利润，那自然是零

dfs(-1,1)表示前-1天持有股票的利润，这显然是不合法的状态，因为前-1天的时候还不能买股票，更不能卖，所以返回负无穷

		if(i<0)if(status==true)   return INT_MIN;else    return 0;

3.本层逻辑

如递推公式所说，我有股票，那就从有股票的两种情况选个最大的

没有股票就从没有股票的两种情况选个最大的

		if(status==1)return max(dfs(i-1,1,prices),-prices[i]);else    return max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);

完整代码：

当然，这是超时的

class Solution {
public:int dfs(int i,int status,vector<int>& prices){if(i<0)if(status==true)   return INT_MIN;else    return 0;if(status==1)return max(dfs(i-1,1,prices),-prices[i]);else    return 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.记忆化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

class Solution {
public:int dfs(int i,int status,vector<int>& prices,vector<vector<int>>& dp){if(i<0)if(status==true)   return INT_MIN;else    return 0;if(dp[i][status]!=-1)return dp[i][status];if(status==1)return dp[i][status]=max(dfs(i-1,1,prices,dp),-prices[i]);else    return 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.1:1翻译为动态规划

1.确定dp数组以及下标的含义

dp数组是前i天可以取得的最大利润

下标笔者采用dp的i对应prices的i-1，防止dp数组下标出现负数（影响的知识dp数组中的位置，对结果不影响的）

也会给出dp数组和prices下标对应的，即dp数组下标就是天数

2.确定递推公式

//第i天没股票
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
//第i天有股票
dp[i][1]=max(dp[i-1][1],-prices[i]);

dp[i+1][0]=max(dp[i][0],dp[i][1]+prices[i]);
dp[i+1][1]=max(dp[i][1],-prices[i]);

3.dp数组如何初始化

DP数组下标从0开始

第0天没有股票，利润为0，dp[0][0]=0;

第0天有股票，那肯定买的第0天的，利润为-prices[i]，dp[0][1]=-prices[i];

DP数组下标从1开始

dfs中的第-1天对应dp的第0天

//dfs(-1,0)对应dp[0][0]
//dfs(-1,1)对应dp[0][1]
dp[0][0]=0;
dp[0][1]=INT_MIN;

和回溯中终止条件对应

4.确定遍历顺序

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

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

完整代码

//避免出现负数下标的情况 dp下标从1开始
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size()+1,vector<int>(2,0));dp[0][0]=0;dp[0][1]=INT_MIN;for(int i=0;i<prices.size();i++){dp[i+1][0]=max(dp[i][0],dp[i][1]+prices[i]);dp[i+1][1]=max(dp[i][1],-prices[i]);}   return dp[prices.size()][0];}
};

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

122.买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

这样的表示状态转移的图叫做状态机，从图中可以明显的看出状态的转移

结合灵神的图更好理解

和上一题的区别就是，这里的股票可以买卖多次

体现在如果我第i天有股票的话，我可能前面买过股票

 dfs(i,1)=max(dfs(i-1,1,prices),dfs(i-1,0,prices)-prices[i]);

而上一题是

dfs(i,1)=max(dfs(i-1,1),-prices[i])

直接写-prices[i]（其实是0-prices[i]）是因为如果你在第i天买进，前面肯定没买过，因为上一题只能买一次，0到i-1天的最大利润只可能是0

本题是前面可能买卖过，可能0到i-1天的最大利润不为0

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-1,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);}
};

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

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-1,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);}
};

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

3.动态规划

这里的dp数组下标是从0开始的

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

和记忆化搜索对应的

dp数组下标从1开始，避免了负数下标的状态

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