121. 买卖股票的最佳时机 - 力扣（LeetCode）
思路：两个状态，前i-1天持有和第i天买入-prices[i]比较。
前i-1天没买入保持现状和第i天卖出dp[i-1][0]+prices[i]比较
重点： dp[i][0]=max(dp[i-1][0],-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2,0));//dp[i][0]表示持有，dp[i][1]表示不持有dp[0][0]=-prices[0];//第一天持有，一定是第一天买入的for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],-prices[i]);//前i-1天持有和第i天买入-prices[i]比较dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);//前i-1天没买入保持现状和第i天卖出dp[i-1][0]+prices[i]比较}return dp[n-1][1];}
};122. 买卖股票的最佳时机 II - 力扣（LeetCode）
思路：前i-1天持有和前i-1天不持有今天买入dp[i][1]-prices[i]比较
前i-1天没买入保持现状和前i-1天买入今天卖出dp[i][0]+prices[i]比较
重点：dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i][0]+prices[i]);
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2,0));//dp[i][0]表示持有所得现金，dp[i][1]表示不持有所得现金dp[0][0]=-prices[0];//第一天持有，一定是第一天买入的for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);//前i-1天持有和前i-1天不持有今天买入dp[i][1]-prices[i]比较dp[i][1]=max(dp[i-1][1],dp[i][0]+prices[i]);//前i-1天没买入保持现状和前i-1天买入今天卖出dp[i][0]+prices[i]比较}return dp[n-1][1];}
};123. 买卖股票的最佳时机 III - 力扣（LeetCode）
思路：五个状态
- 没有操作 （可以不设置这个状态）
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
重点： dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);//第一次持有
dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);//第一次卖出
dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);//第二次持有
dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);//第二次卖出
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(5,0));dp[0][1]=dp[0][3]=-prices[0];//第一次买入和第二次买入第一天for(int i=1;i<n;i++){dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);//第一次持有dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);//第一次卖出dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);//第二次持有dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);//第二次卖出}return dp[n-1][4];}
};总结
两个状态，持有和不持有。持有是前几天买入没有卖出的状态和今天刚刚买入的状态。不持有是前几天卖出和今天卖出的状态。dp数组初始化第一天持有就一定是第一天买入的。今天依赖前几天的状态取最大值。