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

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

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

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

思路

构建数组dp[k][i]，代表在第i天的第k笔交易时，我们获取到的最大收益。

在第i天的第k笔交易时，如果我们不进行对股票进行买卖，那么收益和前一天是一样的，即dp[k][i-1]。

如果我们在i天卖出在j天买的股票，那么第i天时，我们的总收益是prices[i]-prices[j]+dp[k-1][j-1]。我们可以将之前得到的收益和之前买股票时花的钱进行抵消，即将prices[i]-prices[j]+dp[k-1][j-1]写成prices[i]-(prices[j]-dp[k-1])。

由此得出第一种解法。

解法一

//算法复杂度O(kn^2),空间复杂度O(kn)
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;
    vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
    for (int k = 1; k <= 2; k++) {
      for (int i = 1; i < prices.size(); i++) {
        int minCost = prices[0];
        for (int j = 1; j < i; j++) {
          minCost = min(minCost, prices[j] - dp[k - 1][j - 1]);
        }
        dp[k][i] = max(dp[k][i - 1], prices[i] - minCost);
      }
    }
    return dp[2][prices.size() - 1];
  }
};

解法2

prices[i]-(prices[j]-dp[k-1])中，j是始终小于i的，因为根据我们在思路里的描述，j天肯定在i天之前。那么，如果我们让j=i，根据我们在思路里的描述，这相当于是在i天里买股票再将股票卖出去，实际上对我们的结果没有影响。所以，可以将j用i来代替。

于是，代码变成了这样。

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;
    vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
    for (int k = 1; k <= 2; k++) {
      for (int i = 1; i < prices.size(); i++) {
        int minCost = prices[0];
        for (int j = 1; j <= i; j++) { //与代码1不同的地方是此处
          minCost = min(minCost, prices[j] - dp[k - 1][j - 1]);
        }
        dp[k][i] = max(dp[k][i - 1], prices[i] - minCost);
      }
    }
    return dp[2][prices.size() - 1];
  }
};

可以看到，j和i是等价的，我们自然可以将两个循环改成一个循环。

//算法复杂度O(kn),空间复杂度O(kn)
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;
    vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
    for (int k = 1; k <= 2; k++) {
      int minCost = prices[0];
      for (int i = 1; i < prices.size(); i++) {
        minCost = min(minCost, prices[i] - dp[k - 1][i - 1]);
        dp[k][i] = max(dp[k][i - 1], prices[i] - minCost);
      }
    }
    return dp[2][prices.size() - 1];
  }
};

解法3

进一步地，我们可以将解法二的代码里面的两个循环交换下位置。

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;

    vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
    vector<int> minCost(3, prices[0]);

    for (int i=1;i<prices.size();i++){
        for(int k=1;k<=2;k++){
            minCost[k]=min(minCost[k], prices[i]- dp[k-1][i-1]);
            dp[k][i]=max(dp[k][i-1],prices[i]-minCost[k]);
        }
    }  

    return dp[2][prices.size() - 1];
  }
};

可以轻易地发觉，dp[k][i]只由其更新前的一项值决定，所以可以对其进行压缩。

//时间复杂度O(kn)，空间复杂度O(k)
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;

    vector<int> dp(3, 0);
    vector<int> minCost(3, prices[0]);

    for (int i=1;i<prices.size();i++){
        for(int k=1;k<=2;k++){
            minCost[k]=min(minCost[k], prices[i]- dp[k-1]);
            dp[k]=max(dp[k],prices[i]-minCost[k]);
        }
    }  

    return dp[2];
  }
};