当前位置：首页 > news >正文

【c++刷题笔记-动态规划】day41： 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II 、

news 来源：原创 2024/9/21 14:30:11

121. 买卖股票的最佳时机 - 力扣（LeetCode）

思路：两个状态，前i-1天持有和第i天买入-prices[i]比较。

前i-1天没买入保持现状和第i天卖出dp[i-1][0]+prices[i]比较

重点： dp[i][0]=max(dp[i-1][0],-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2,0));//dp[i][0]表示持有，dp[i][1]表示不持有dp[0][0]=-prices[0];//第一天持有，一定是第一天买入的for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],-prices[i]);//前i-1天持有和第i天买入-prices[i]比较dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);//前i-1天没买入保持现状和第i天卖出dp[i-1][0]+prices[i]比较}return dp[n-1][1];}
};

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

思路：前i-1天持有和前i-1天不持有今天买入dp[i][1]-prices[i]比较

前i-1天没买入保持现状和前i-1天买入今天卖出dp[i][0]+prices[i]比较

重点：dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i][0]+prices[i]);

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2,0));//dp[i][0]表示持有所得现金，dp[i][1]表示不持有所得现金dp[0][0]=-prices[0];//第一天持有，一定是第一天买入的for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);//前i-1天持有和前i-1天不持有今天买入dp[i][1]-prices[i]比较dp[i][1]=max(dp[i-1][1],dp[i][0]+prices[i]);//前i-1天没买入保持现状和前i-1天买入今天卖出dp[i][0]+prices[i]比较}return dp[n-1][1];}
};

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

思路：五个状态

没有操作（可以不设置这个状态）
第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

重点： 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]);//第二次卖出

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(5,0));dp[0][1]=dp[0][3]=-prices[0];//第一次买入和第二次买入第一天for(int i=1;i<n;i++){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];}
};