一文解决股票交易问题

终于到动态规划的最后一部分啦，完结撒花~

这一篇总结【股票交易问题】，参考的是labuladong的文章

相关问题有：

• 121，买卖股票的最佳时机

• 122，买卖股票的最佳时机Ⅱ

• 309，最佳买卖股票时机含冷冻期

• 714，最佳买卖股票时机含手续费

• 123，买卖股票的最佳时机Ⅲ

• 188，买卖股票的最佳时机Ⅲ

做题思路

对股票，每天有三种选择：买入、卖出、保持不变。注意卖出必须在买入之后，买入必须在卖出之后，保持不变分为两种状态：一种是买入之后的持有股票，一种是卖出之后的不持有股票。

1. 子问题

   \(dp[i][k][s]\) — 在第 i 天，交易次数最多为 k，持有状态为 s 的最大利润。其中，0 =< i <= n - 1 , k >= 1，s = 0 或 1。

2. base case

   \(dp[-1][k][0] = 0\)

   解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。

   \(dp[-1][k][1] = -infinity\)

   解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。

   \(dp[i][0][0] = 0\)

   解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。

   \(dp[i][0][1] = -infinity\)

   解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

3. 状态转移方程

   \(dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])\)

   解释：今天没有持有股票，有两种可能：

   要么是昨天就没有持有，然后今天保持不变；要么是昨天持有股票，但是今天卖出了，所以今天没有持有股票。

   \(dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])\)

   解释：今天持有着股票，有两种可能：

   要么昨天就持有着股票，然后今天保持不变；要么昨天本没有持有，但今天买入，所以今天就持有股票了。

4. 返回值

   \(dp[n - 1][k][0]\) — 最后一天，最多允许 K 次交易，最多获得多少利润。[0] 表示手上的股票已经卖出去了，很显然最后一天不持有股票得到的利润一定更大。

再将此思路运用到下面题目：

121，买卖股票的最佳时机，easy

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

• 思路：

  按照套路模板， k = 1时状态转移方程为：

  \(dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])\)

  \(dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) =max(dp[i-1][1][1], -prices[i])\)

  k 对状态转移没有影响，可简化为两个状态。

  1. 子问题

     $ dp[i][s]$ — 第 i 天 持有状态为 s = 0 或 1 的 最大利润。

  2. base case

     \(dp[0][0] = 0\) 最开始一天，没有持有股票，利润为0。

     \(dp[0][1] = - prices[0]\) 最开始一天，持有股票，利润为 - 买入价钱。

  3. 状态转移方程

     从第二天开始遍历

     \(dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])\)

     \(dp[i][1] = max(dp[i-1][1], -prices[i])\)

• 代码：

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[][] dp = new int[n][2];
          //base case
          dp[0][0] = 0;
          dp[0][1] = -prices[0];
  
          for(int i = 1; i < n; i++){
              // int price = prices[i];
              dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
              dp[i][1] = Math.max(dp[i - 1][1], - prices[i]);
          }
          return dp[n - 1][0];
      }
  }

  • 关于base case 的解释：

    i ∈[0, n - 1]，在循环中可能会出现 i 为 -1 的情况

    for (int i = 0; i < n; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
    }

    需要对 i - 1 == -1 进行处理

    if (i - 1 == -1) {
            dp[i][0] = 0;
            // 解释：
            //   dp[i][0] 
            // = max(dp[-1][0], dp[-1][1] + prices[i])
            // = max(0, -infinity + prices[i]) = 0
            dp[i][1] = -prices[i];
            //解释：
            //   dp[i][1] 
            // = max(dp[-1][1], dp[-1][0] - prices[i])
            // = max(-infinity, 0 - prices[i]) 
            // = -prices[i]
        }

    放在 i = 0开始的循环中判断。为了简化将 i = 0提出，再从 i = 1 第二天开始循环，即上面所示代码。

• 状态压缩

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[] dp = new int[2];
          //base case
          dp[0] = 0;
          dp[1] = -prices[0];
  
          for(int i = 1; i < n; i++){
              // int price = prices[i];
              dp[0] = Math.max(dp[0], dp[1] + prices[i]);
              dp[1] = Math.max(dp[1], - prices[i]);
          }
          return dp[0];
      }
  }

• 其他方法：一次遍历，找到最低点买入，卖出一定在买入之后，即找到最大差值时卖出。

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length == 0 || prices == null) return 0;
          int min = prices[0];//最低点
          int maxPro = 0;//最大利润
          for(int i = 1; i < prices.length; i++){
              if(min > prices[i]) 
                  min = prices[i];
              else if(maxPro < prices[i] - min) 
                  maxPro = prices[i] - min;
          }
          return maxPro;
      }
  }

122，买卖股票的最佳时机Ⅱ，easy

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

• 思路：

  与上面的区别仅在于 k = + 无穷，就可以认为 k = k - 1。模板的状态转移方程为：

  dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              = max(dp[i-1][k][1], dp[i-1][k][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-1][0] - prices[i])

• 代码：

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[][] dp = new int[n][2];
          //base case
          dp[0][0] = 0;
          dp[0][1] = -prices[0];
  
          for(int i = 1; i < n ; i++){
              dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
              dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
          }
          return dp[n - 1][0];
      }
  }

• 状态压缩：

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[] dp = new int[2];
          //base case
          dp[0] = 0;
          dp[1] = -prices[0];
  
          for(int i = 1; i < n ; i++){
              dp[0] = Math.max(dp[0], dp[1] + prices[i]);
              dp[1] = Math.max(dp[1], dp[0] - prices[i]);
          }
          return dp[0];
      }
  }

309，最佳买卖股票时机含冷冻期，medium

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

• 思路：

  与上一题相同在 k = + 无穷，不同在 卖出股票的第二天不能进行交易。

  • 状态转移方程

    在上一题的状态转移方程上 \(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])\) 修改。如果今天持有股票，可能前一天持有保持不变，也可能之前没有股票，今天买入。但题中一天的冷静期说明今天持有的状态要在冷静期之前的状态上改变，则 \(dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])\)

  • base case

    如果按照上面从第二天开始循环，会出现 \(dp[-1]\) 的情况，所以要多处理个 $dp[1] $

• 代码：

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[][] dp = new int[n][2];
          //base case
          dp[0][0] = 0;
          dp[0][1] = - prices[0];
          dp[1][0] = Math.max(0, prices[1] - prices[0]);
          dp[1][1] = Math.max(-prices[0], -prices[1]);
          
          for(int i = 2; i < n; i++){
              dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
              dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
          }
          return dp[n - 1][0];
      }
  }

714，最佳买卖股票时机含手续费，medium

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路：

与122题相同在 k = +无穷，不同在 卖出股票需要支付手续费。

• 状态转移方程

  在上一题的状态转移方程上 \(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])\) 修改。一次交易需要支付一次手续费，则只在卖出时考虑交费，则 \(dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)\)

• 代码：

  class Solution {
      public int maxProfit(int[] prices, int fee) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[][] dp = new int[n][2];
          //base case
          dp[0][0] = 0;
          dp[0][1] = -prices[0];
  
          for(int i = 1; i < n ; i++){
              dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
              dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
          }
          return dp[n - 1][0];
      }
  }

• 状态压缩

  class Solution {
      public int maxProfit(int[] prices, int fee) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[] dp = new int[2];
          //base case
          dp[0] = 0;
          dp[1] = -prices[0];
  
          for(int i = 1; i < n ; i++){
              dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
              dp[1] = Math.max(dp[1], dp[0] - prices[i]);
          }
          return dp[0];
      }
  }

123，买卖股票的最佳时机Ⅲ，hard

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

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

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

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

• 思路：

  此题与上面的题不同在于：上面的题目中 k 都被化简掉了。但此题 k 由于没有消掉 k 的影响，所以必须要对 k 进行穷举，除了遍历 i，还要遍历 k。

• 代码：

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int max_k = 2;
          int[][][] dp = new int[n][max_k + 1][2];
  
          // dp[0][1][0] = 0;
          // dp[0][2][0] = 0;
          // dp[0][1][1] = -prices[0];
          // dp[0][2][1] = -prices[0];
  
          for(int i = 0; i < n; i++){
              for(int k = max_k; k >= 1; k--){
                  处理base case
                  if(i - 1 == -1){
                      dp[i][1][0] = 0;
                      dp[i][2][0] = 0;
                      dp[i][1][1] = -prices[i];
                      dp[i][2][1] = -prices[i];
                      continue;
                      //dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]) = max(0,-无穷) = 0
                      //dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]) = max(0,-无穷) = 0
                      //dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][0][0] - prices[i]) = max(-无穷, -prices[i]) = -prices[i]
                      //dp[i][2][1] = max(dp[i-1][2][1],dp[i-1][0][0] - prices[i]) = max(-无穷, -prices[i]) = -prices[i]
                  }
                 dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                 dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
              }
          }
          return dp[n - 1][max_k][0];
      }
  }

188，买卖股票的最佳时机Ⅲ，hard

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔 交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

• 思路：

  与上一题区别在于完成 k 笔交易，有了上一题的铺垫，此题的代码很好解决。但按照上面的思路，k 太大会出现超出内存限制。思考：交易数k 最大有多大呢？

  一次交易分为买入和卖出，至少需要两天。所以有效的限制 k <= n / 2，如果超过，就没有约束作用了，相当于 k = +无穷（即第122题）。

• 代码：

  class Solution {
      public int maxProfit(int k, int[] prices) {
          if(prices.length < 2 || k < 1) return 0;
          int n = prices.length;
          int[][][] dp = new int[n][k + 1][2];
  
          if(k > n / 2){
              return maxProfit(prices);
          }
  
          for(int i = 0; i < n; i++){
              for(int j = k; j >= 1; j--){
                  //处理base case
                  if(i - 1 == -1){
                      dp[i][j][0] = 0;
                      dp[i][j][1] = -prices[i];
                      continue;
                      }
                 dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                 dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
              }
          }
          return dp[n - 1][k][0];
      }
      public int maxProfit(int[] prices) {
          if(prices.length < 2) return 0;
          int n = prices.length;
          int[][] dp = new int[n][2];
          //base case
          dp[0][0] = 0;
          dp[0][1] = -prices[0];
  
          for(int i = 1; i < n ; i++){
              dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
              dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
          }
          return dp[n - 1][0];
      }
  }