代码随想录算法训练营第五十天|123.买卖股票的最佳时机III、

123.买卖股票的最佳时机III  

动态规划五部曲

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

一天一共就有五个状态，

没有操作 （其实我们也可以不设置这个状态）

第一次持有股票

第一次不持有股票

第二次持有股票

第二次不持有股票

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

确定递推公式

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数组初始化

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 

动规五部曲

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

至多有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数组初始化

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