123.買賣股票的最佳時機III??

動態(tài)規(guī)劃五部曲

確定dp數(shù)組以及下標的含義

一天一共就有五個狀態(tài)，

沒有操作 （其實我們也可以不設置這個狀態(tài)）

第一次持有股票

第一次不持有股票

第二次持有股票

第二次不持有股票

dp[i][j]中 i表示第i天，j為 [0 - 4] 五個狀態(tài)，dp[i][j]表示第i天狀態(tài)j所剩最大現(xiàn)金

確定遞推公式

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

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

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]);

dp數(shù)組初始化

dp[0][0] = 0

dp[0][1] = -prices[0]

dp[0][2] = 0

dp[0][3] = -prices[0];

dp[0][4] = 0

intmaxProfit(vector<int>&prices){if(prices.size()==0)return0;vector<vector<int>>dp(prices.size(),vector<int>(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(inti=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]);}returndp[prices.size()-1][4];}

188.買賣股票的最佳時機IV?

動規(guī)五部曲

確定dp數(shù)組以及下標的含義

至多有K筆交易，那么j的范圍就定義為 2 * k + 1?

vector<vector<int>>dp(prices.size(),vector<int>(2*k+1,0));

確定遞推公式

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

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

for(intj=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}

dp數(shù)組初始化

dp[0][0] = 0

dp[0][1] = -prices[0]

dp[0][2] = 0

dp[0][3] = -prices[0]

dp[0][4] = 0

for(intj=1;j<2*k;j+=2){dp[0][j]=-prices[0];}

確定遍歷順序

從前向后遍歷

最后一次賣出，一定是利潤最大的，dp[prices.size() - 1][2 * k]即紅色部分就是最后求解

intmaxProfit(intk,vector<int>&prices){if(prices.size()==0)return0;vector<vector<int>>dp(prices.size(),vector<int>(2*k+1,0));for(intj=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(inti=1;i<prices.size();i++){for(intj=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}returndp[prices.size()-1][2*k];}