leetcode_day43

今日内容：股票专题日🤑

• 121. 买卖股票的最佳时机 easy
• 122. 买卖股票的最佳时机Ⅱ medium
• 123. 买卖股票的最佳时机Ⅲ hard

121. 买卖股票的最佳时机

题目：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：

很明显的状态转移，昨天买了和昨天没有买两种情况，昨天买了今天就卖或者持有，昨天没买今天就买或者继续观望，最后返回今天卖了或不卖中的最大值。

代码

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int len = prices.size();
    vector<vector<int>> dp(2, vector<int>(2));
    dp[0][0] -= prices[0];
    dp[0][1] = 0;
    for (int i = 1; i < len; i++) {
      dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);//昨天买了；昨天没买今天买
      dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);//昨天没买；昨天买了今天卖
    }
    return dp[(len - 1) % 2][1];//卖了肯定比拿手里强，返回卖了的
  }
};

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

题目：

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路：

与上一题的区别在于，这题可以多次买卖，如果按贪心来做的话，直接累积上升就可以。

按dp来做，仍然保留买与没买的状态区别，对于买的状态要修改，上一道题只能买一次，所以买必定是第一次，从0开始算盈亏。这里就需要记录之前的盈亏，因为买不一定是第一次。

代码

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    //dp非滚动写法
    vector<vector<int>> dp(2, vector<int>(2));
    dp[0] = {-prices[0], 0};//0买，1不买
    for(int i = 1;i < prices.size();i++) {
      //与上一题的区别：-prices[i]变成了dp[i-1 % 2][1] - prices[i]，在昨天没买的基础上计算
      dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]); //i天买，昨天买了不能再买/昨天没买今天买
      dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]); //i天不买，昨天没买/昨天买了今天卖掉
    }
    return dp[(prices.size() - 1) % 2][1];
  }
};

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

题目：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：

只能买两次，所以变复杂了很多，不愧是hard，一下给我干趴下了，思路是抄的，没想出来😭

根据之前的经验，可以分为买和不买两种状态，由于这里只能买卖两次，所以分为四种状态（或者说 阶段 ）：

• 第一次还没买
• 第一次买了在手里
• 第二次还没买（第一次已经卖掉了）
• 第二次卖掉了

每个状态都可以如之前一样分别由昨天和今天来得到，取最大值，于是得到如下代码

代码

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];// 相当于第一天买了卖再买，可不能设成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];//
  }
};