买卖股票的最佳时机1

之前贪心算法有提到过，我们算正区间的总和，只要是正区间就加入总和

dp[i][0]表示第i天持有该股票的最大收益，dp[i][1]表示第i天不持有该股票的最大收益

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

买卖股票的最佳时机2

唯一不同的就是， dp[i%2][0]=max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);昨天不持有股票的所得现金减去 今天的股票价格

买卖股票的最佳时机3

至多买卖两次，那么状态数增加至5种，分析清楚状态即可轻松解决

0没有操作 （其实我们也可以不设置这个状态）
1第一次持有股票
2第一次不持有股票
3第二次持有股票
4第二次不持有股票

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size()==0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(int i=1;i<prices.size();i++){//dp[i][0]=dp[i-1][0];dp[i][1]=max(dp[i-1][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[prices.size()-1][4];}
};

思路竟然和之前做过的一个斐波那契四季果树问题类似