买卖股票的最佳时机III

动态规划-分两小组分别计算（超时）

class Solution {
public:int partprofit( vector<int>& prices , int start , int end ){if((end-start)<=1) return 0;vector<int> dp(end - start , 0);int min = prices[start];for(int i=1 ; i< end-start ;i++){if(prices[start + i] < min) min = prices[start + i];dp[i] = max(dp[i-1]  , prices[start + i]-min);}// for(auto it:dp) cout<<it<<' ';return dp[ end - start -1];}int maxProfit(vector<int>& prices) {if(prices.size() <= 1) return 0;int val1=0 , val2=0 , maxval=0;for(int i=0 ; i<prices.size(); i++){val1 = partprofit(prices , 0 , i);val2 = partprofit(prices , i ,prices.size());if(val1 + val2 > maxval ) maxval = val1+val2;cout<<val1+val2<<' ';}cout<<endl;return maxval;}
};

动态规划

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

1. 没操作
2. 第一次持有股票（包括之前买的和今天买的）
3. 第一次不持有股票（包括之前没买和今天卖了）
4. 第二次持有股票
5. 第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

确定递推公式

达到持有状态，有两个具体操作：

• 第i天买入股票了，那么dp[i][1/3] = dp[i-1][0/2] - prices[i]
• 第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1/3] = dp[i - 1][1/3]

达到不持有状态，也有两个操作：

• 第i天卖出股票了，那么dp[i][2/4] = dp[i - 1][1/3] + prices[i]
• 第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2/4] = dp[i - 1][2/4]

dp数组如何初始化

• dp[0][0] = 0;
• dp[0][1/3] = -prices[0];
• dp[0][2/4] = 0;

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