笔记：代码随想录算法训练营day41:LeetCode121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

学习资料：代码随想录

121. 买卖股票的最佳时机

力扣题目链接

思路：注意题意只能买卖一次

定义：dp[i][0]表示不持有当前股票，dp[i][1]表示持有当前股票

递推公式：今天持有分之前就持有和今天才买，今天不持有分之前就不持有和今天才卖

初始化：根据递推公式，第一个数组需要初始化一下

遍历顺序：根据递推公式，从前向后

打印：略

// 定义：dp[i][0]为不持有当前股票的利润，dp[i][1]为持有当前股票的利润
// 递推公式：有四种情况：当前持有分为今天买的和之前就买了两种；当前没有分为今天卖的和之前就没有两种情况
// 初始化：第一天的就卖或不买两种情况，即持有和不持有两种情况，要初始化一下
// 遍历：从1开始
// 打印
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,0));dp[0][0] = 0;dp[0][1] = -prices[0];for(int i =1;i<prices.size();i++){dp[i][0] = max(dp[i-1][0],prices[i]+dp[i-1][1]);   //卖的话的减去之前买的最小价格dp[i][1] = max(dp[i-1][1],-prices[i]);             //只能卖一次}return dp[prices.size()-1][0];}
};

正好复习一下贪心：

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

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

力扣题目链接

思路：出奇得是，其实改动并不需要很多

在第一题的基础上，只需要在递推公式处作一点改动：在持有的情况不是第一天持有了，应该算上之前的利润

// 递推公式：今天持有：昨天就持有和昨天不持有今天买的，在这里今天买的可能是昨天卖过了
//           今天不持有：昨天不持有和今天卖的
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,0));dp[0][0] = 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 dp[prices.size()-1][0];}
};

复习一下贪心：

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

 

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

力扣题目链接

思路：

定义：dp[i][0]为没有操作；dp[i][1]为第一次持有，dp[i][2]为第一次卖出，dp[i][3]为第二次持有，dp[i][4]为第二次卖出（不持有）

递推公式：跟第一题差不多，是两个情况比较

初始化：这下要初始化五个了，其实也可以是四个，那样定义的第一个就不用了

遍历顺序：顺着走

打印：略

// 五部曲：相当于第一题的一个延伸了
// 定义：dp[i][0]为不进行操作，dp[i][1]为第一次持有，dp[i][2]为第一次不持有，dp[i][3]为第二次持有，dp[i][4]为第二次不持有
// 递推：还是四种情况：持有包括之前就持有和今天买一支，不持有包括之前就不持有和今天卖掉，那这样其实不操作的话是可以省略的
// 初始化：这里真是有意思，一支股票可以在一天内被卖来卖去的，在买之前卖了就行
// 打印
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(5,0));dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;        //当天买，当天卖dp[0][3] = -prices[0];  //当天卖完当天还买dp[0][4] = 0;           //一天内买卖了两次for(int i = 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]);}return dp[prices.size()-1][4];}
};

不用dp[0][0]的写法：

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(5,0));//dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;        //当天买，当天卖dp[0][3] = -prices[0];  //当天卖完当天还买dp[0][4] = 0;           //一天内买卖了两次for(int i = 1;i<prices.size();i++){//dp[i][0] = dp[i-1][0];dp[i][1] = max(dp[i-1][1],-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[prices.size()-1][4];}
};