代码随想录第四十六天打卡

股票问题是一个动态规划的系列问题，前两题并不难，第三题有难度。

121. 买卖股票的最佳时机

视频讲解：动态规划之 LeetCode：121.买卖股票的最佳时机1_哔哩哔哩_bilibili

代码随想录

class Solution {
public:int maxProfit(vector<int>& prices) {int mi=INT_MAX;int res=0;for (int i=0;i<prices.size();i++){mi=min(prices[i],mi);res=max(prices[i]-mi,res);}return res;}
};

总结

我觉得这道题贪心更快一些。

122.买卖股票的最佳时机II

视频讲解：动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II_哔哩哔哩_bilibili

代码随想录

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

总结

竟然先把第二题写出来了。

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

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

视频讲解：动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III_哔哩哔哩_bilibili

代码随想录

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size(),vector<int>(5,0));dp[0][1]=-prices[0];//0表示没买，1表示第一次买入，2表示第一次卖出，3表示第二次买入，4表示第二次卖出。dp[0][3]=-prices[0];//可以再第一天买了再卖,所以要进行初始化for (int i=1;i<prices.size();i++){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][2]-prices[i],dp[i-1][3]);dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4]);}return dp[prices.size()-1][4];}
};