day-50 代码随想录算法训练营（19）动态规划 part 11

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

分析：只能买卖两次，就是说有五个状态：

• 没有买过
• 第一次买入
• 第一次卖出
• 第二次买入
• 第二次卖出

思路：二维数组，记录五个状态

• 1.dp存储：dp[i][1] 第一次买入   dp[i][2] 第一次卖出  dp[i][3] 第二次买入  dp[i][4] 第二次卖出
• 2.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])
• 3.初始化：dp[0][1]=-prices[0]    dp[0][3]=-prices[0]
• 4.遍历顺序：1~n

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

188.买卖股票的最佳时机IV

分析：买卖几次成了变量

思路：

• 1.dp存储：2k+1个状态的买卖金额
• 2.动态转移方程（递推式）：
  • j奇数：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
  •  j偶数：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
• 3.初始化：j奇数：dp[i][j]=-prices[0]
• 4.遍历顺序：1-n

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n=prices.size();int m=k*2;vector<vector<int>>dp(n,vector<int>(m+1,0));for(int i=1;i<=m;i+=2) dp[0][i]=-prices[0]; //初始化for(int i=1;i<n;i++){dp[i][0]=dp[i-1][0];//第一天不持有for(int j=1;j<m+1;j++){if(j%2!=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);//第j天持有else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);//第j天卖出}}return dp[n-1][m];}
};

309.买卖股票的最佳时机含冷冻期

分析：现在有四种状态：买入股票 冷冻期后没买入   卖出股票   冷冻期

思路：dp存储四种状态

• 1.dp存储：四种状态
• 2.动态转移方程（递推式）:
  • dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]))
  • dp[i][1]=max(dp[i-1][1],dp[i-1][3])
  • dp[i][2]=dp[i-1][0]+prices[i]
  • dp[i][3]=dp[i-1][2]
• 3.初始化：dp[0][0]=-prices[0]
• 4.遍历顺序：1~n

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(4,0));dp[0][0]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));//持有dp[i][1]=max(dp[i-1][1],dp[i-1][3]);//冷冻期后面不持有dp[i][2]=dp[i-1][0]+prices[i];//卖出dp[i][3]=dp[i-1][2];//冷冻期}return max(dp[n-1][3],max(dp[n-1][1],dp[n-1][2]));//最大值一定不持有}
};