股票问题系列通解

> 本篇文章转载自[ 股票问题系列通解（转载翻译）](https://leetcode-cn.com/circle/article/qiAgHn)。

## 1 前言

1. 股票问题一共有六道题，链接如下：
   * [121. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock)。
   * [122. 买卖股票的最佳时机 II]()。
   * [123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii)。
   * [188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv)。
   * [309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown)。
   * [714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee)。
2. 每个问题都有优质的题解，但是大多数题解没有建立起这些问题之间的联系，也没有给出股票问题系列的通解，这篇文章给出适用于全部股票问题的通解，以及对于每个特定问题的特解。

## 2 通用情况

1. 这个想法基于如下问题，**给定一个表示每天股票价格的数组**，**什么因素决定了可以获得的最大收益**，相信大多数人可以很快给出答案，例如**在那些天进行交易以及允许多少次交易**，这些因素当然也很重要，在问题描述中也有这些因素，然而还有一个隐藏但是关键的因素决定了最大收益，下文将阐述这一点。
2. 首先介绍一些符号：
   1. 用 $n$**表示股票价格的数组**。
   2. 用 $i$**表示第 $i$ 天**（$i$ 的取值范围是 0 到 $n - 1$）。
   3. 用 $k$**表示允许的最大交易次数**。
   4. 用 $T[i][k]$**表示在第 $i$ 天结束时**，**最多进行 $k$ 次交易的情况下可以获得的最大收益**。
3. **基准情况为 $T[-1][k] = T[i][0] = 0$**，**表示没有进行股票交易时没有收益**（注意第一天对应 $i = 0$，因此 $i = -1$ 表示没有股票交易）。
4. 现在开始**将 $T[i][k]$ 关联到子问题**，**得到状态转移方程**：
   1. **第 $i$ 天可能有三个操作**，分别为**买入**、**卖出**、**休息**。
   2. 我们并**不知道哪个操作是最好的**，但是**可以通过计算得到选择每个操作可以得到的最大收益**，**假设没有别的限制条件**，则**可以尝试每一种操作**，并**选择可以最大化收益的一种操作**，但是，**题目中确实有限制条件**，**规定不能同时进行多次交易**，因此**如果决定在第 $i$ 天买入**，**在买入之前必须持有 0 份股票**，**如果决定在第 $i$ 天卖出**，**在卖出之前必须恰好持有 1 份股票**，**持有股票的数量是上文提及到的隐藏因素**，**该因素影响第 $i$ 天可以进行的操作**，**进而影响最大收益**。
   3. 因此对 $T[i][k]$ 的定义需要分成两项：
      1. $T[i][k][0]$**表示第 $i$ 天结束时**，**最多进行 $k$ 次交易且在进行操作后持有 0 份股票的情况下可以获得的最大收益**。
      2. $T[i][k][1]$**表示在第 $i$ 天结束时**，**最多进行 $k$ 次交易且在进行操作后持有 1 份股票的情况下可以获得的最大收益**。
   4. 使用新的状态表示之后，可以得到基准情况和状态转移方程如下：
      1. **基准情况**：

$$
         T[-1][k][0] = 0, T[-1][k][1] = -Infinity
         $$

$$
         T[i][0][0] = 0, T[i][0][1] = -Infinity
         $$

1. 基准情况中，$T[-1][k][0] = T[i][0][0] = 0$ 的含义和上文相同，$T[-1][k][1] = T[i][0][1]$ 的含义是**在没有进行股票交易时不允许持有股票**。
      2. **状态转移方程**：

$$
         T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
         $$

$$
         T[i][k][1] = max(T[i - 1][k - 1][0] - prices[i], T[i - 1][k][1])
         $$

1. **对于状态转移方程中的**$T[i][k][0]$，**第 $i$ 天进行的操作只能是休息或卖出**，因为**在第 $i$ 天结束时持有的股票数量是 0**，$T[i - 1][k][0]$**是休息操作可以得到的最大收益**，$T[i - 1][k][1] + prices[i]$**是卖出操作可以得到的最大收益**，**注意到允许的最大交易次数是不变的**，因为**每次交易包含两次成对的操作**，分别为**买入**和**卖出**，**只有买入操作会改变允许的最大交易次数**。
         2. **对于状态转移方程中的 $T[i][k][1]$**，**第 $i$ 天进行的操作只能是休息或卖出**，因为**在第 $i$ 天结束时持有的股票数量是 0**，$T[i - 1][k][1] + prices[i]$**是卖出操作可以得到的最大收益**，$T[i - 1][k - 1][0] - prices[i]$**是买入操作可以得到的最大收益**，**注意到允许的最大交易次数减少了一次**，因为**每次买入操作会使用一次交易**。
   5. **为了得到最后一天结束时的最大收益**，**可以遍历股票价格数组**，**根据状态转移方程计算 $T[i][k][0]$ 和 $T[i][k][1]$ 的值**，**最终答案是 $T[n - 1][k][0]$**，因为**结束时持有 0 份股票的收益一定大于持有 1 份股票的收益**。

## 3 应用于特殊情况

上述六个股票问题是**根据 $k$ 的值进行分类**的，其中 $k$**是允许的最大交易次数**，**最后两个问题有附加限制**，**包括【冷冻期】和【手续费】**，**通解可以应用于每个股票问题**。

### 3.1 情况一：$k = 1$

1. 情况一对应的题目是[121. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock)。
2. 对于情况一，**每天有两个未知变量**，分别为 $T[i][1][0]$ 和 $T[i][1][1]$，状态转移方程如下：

$$
   T[i][1][0] = max(T[i - 1][1][0], T[i - 1][1][1] + prices[i])
   $$

$$
   T[i][1][1] = max(T[i - 1][1][1], T[i - 1][0][0] - prices[i]) = max(T[i - 1][1][1], -prices[i])
   $$

第二个状态转移方程利用了 $T[i - 1][0][0] = 0$
3. 根据上述状态转移方程，可以写出时间复杂度为 $O(n)$ 和空间复杂度为 $O(n)$ 的解法。

```java
   /**
    * 121. 买卖股票的最佳时机（版本 3：动态规划）
    * @param prices    股票价格
    * @return  最大利润
    */
   public int maxProfit(int[] prices) {
       if (prices == null || prices.length == 0) {return 0;}

int m = prices.length;
       int[][] dp = new int[m + 1][2];

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

return dp[m - 1][0];
   }
   ```

### 3.2 情况二：$k$ 为正无穷

1. 情况二对应的题目是[122. 买卖股票的最佳时机 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii)。
2. **如果 $k$ 为正无穷**，**则 $k$ 和 $k - 1$ 可以看成是相同的**，因此**有**$T[i - 1][k - 1][0] = T[i - 1][k][0]$**和 $T[i - 1][k - 1][1] = T[i - 1][k][1]$**，**每天仍然有两个未知变量**，**分比为 $T[i][k][0]$ 和 $T[i][k][1]$**，其中 $k$**为正无穷**，状态转移方程如下：

$$
   T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
   $$

$$
   T[i][k][1] = max(T[i - 1][k - 1][0] - prices[i], T[i - 1][k][1]) = max(T[i - 1][k][0] - prices[i], T[i - 1][k][1])
   $$

第二个状态转移方程利用了 $T[i - 1][k - 1][0] = T[i - 1][k][0]$
3. 根据上述状态转移方程，可以写出时间复杂度为 $O(n)$ 和空间复杂度为 $O(n)$ 的解法：

```java
   /**
    * 122. 买卖股票的最佳时机 II
    * @param prices    股票价格
    * @return  最大利润
    */
   public int maxProfit(int[] prices) {
       if (prices == null || prices.length == 0) {return 0;}

int m = prices.length;
       int[][] dp = new int[m + 1][2];

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

return dp[m - 1][0];
   }
   ```

### 3.3 情况三：$k = 2$

1. 情况三对应的题目是[123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii)。
2. 情况三和情况一相似，区别之处是，对于情况三，**每天有四个未知变量**，分别为 $T[i][1][0]$、$T[i][1][1]$、$T[i][2][0]$、$T[i][2][1]$，状态转移方程如下：

$$
   T[i][1][0] = max(T[i - 1][1][0], T[i - 1][1][1] + prices[i])
   $$

$$
   T[i][1][1] = max(T[i - 1][0][0] - prices[i], T[i - 1][1][1]) = max(-prices[i], T[i - 1][1][1])
   $$

$$
   T[i][2][0] = max(T[i - 1][2][0], T[i - 1][2][1] + prices[i])
   $$

$$
   T[i][2][1] = max(T[i - 1][1][0] - prices[i], T[i - 1][2][1])
   $$

第二个状态转移方程利用了 $T[i][0][0] = 0$。
3. 根据上述状态转移方程，可以写出时间复杂度为 $O(n)$ 和空间复杂度为 $O(n)$ 的解法：

```java
   /**
    * 123. 买卖股票的最佳时机 III
    * @param prices    股票价格
    * @return  最大利润
    */
   public int maxProfit(int[] prices) {
       if (prices == null || prices.length == 0) {return 0;}

int m = prices.length;
       int[][][] dp = new int[m + 1][3][2];

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

return dp[m - 1][2][0];
   }
   ```

### 3.4 情况四：$k$ 为任意值

1. 情况四对应的题目是[188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv)。
2. 情况四是**最通用的情况**，**对于每一天需要使用不同的 $k$ 值更新所有的最大收益**，**对应持有 0 份股票或 1 份股票**，**如果 $k$ 超过一个临界值**，**最大收益就不在取决于允许的最大交易次数**，**而是取决于股票价格数组的长度**，因此**可以进行优化**。
3. **一个由有收益的交易至少需要两天**（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格），**如果股票价格数组的长度为 $n$**，则**有收益的交易的数量最多为 $n / 2$**（整数除法），因此 $k$**的临界值是 $n / 2$**，**如果给定的 $k$ 不小于临界值**，即 $k >= n / 2$，则**可以将 $k$ 扩展为正无穷**，**此时问题等价于[情况二](#3-2-情况二--为正无穷)。**
4. 根据状态转移方程，可以写出时间复杂度为 $O(nk)$ 和空间复杂度为 $O(nk)$ 的解法：

```java
   /**
    * 188. 买卖股票的最佳时机 IV
    * @param prices    股票价格
    * @param k 交易最大笔数
    * @return  最大利润
    */
   public int maxProfit(int k, int[] prices) {
       if (prices == null || prices.length == 0) {return 0;}
       if (k >= prices.length / 2) {return maxProfit(prices);}

int m = prices.length;
       int[][][] dp = new int[m + 1][k + 1][2];

for (int i = 0; i <= k; i++) {
           dp[0][i][0] = 0;
           dp[0][i][1] = -prices[0];
       }
       for (int i = 1; i < m; i++) {
           for (int j = k; j > 0; j--) {
               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[m - 1][k][0];
   }

/**
    * 当 k 趋近于无穷大时买卖股票的最佳时机
    * @param prices    股票价格
    * @return  最大利润
    */
   public int maxProfit(int[] prices) {
       if (prices == null || prices.length == 0) {return 0;}

int m = prices.length;
       int[][] dp = new int[m + 1][2];

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

return dp[m - 1][0];
   }
   ```

### 3.5 情况五：$k$ 为正无穷但有冷却时间

1. 情况五对应的题目是[309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown)。
2. 由于具有相同的 $k$ 值，因此**情况五和情况二非常类似**，**不同之处在于情况五有「冷却时间」的限制**，因此**需要对状态转移方程进行一些修改**。
3. 情况二的状态转移方程如下：

$$
   T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
   $$

$$
   T[i][k][1] = max(T[i - 1][k][0] - prices[i], T[i - 1][k][1])
   $$
4. 但是**在有「冷却时间」的情况下**，**如果在第 $i - 1$ 天卖出了股票**，**就不能在第 $i$ 天买入股票**，因此，**如果要在第 $i$ 天买入股票**，**第二个状态转移方程就不能使用 $T[i - 1][k][0]$**，而**应该使用 $T[i - 2][k][0]$**，**状态转移方程中的别的项保持不变**，**新的状态转移方程如下**：

$$
   T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
   $$

$$
   T[i][k][1] = max(T[i - 2][k][0] - prices[i], T[i - 1][k][1])
   $$
5. 根据上述状态转移方程，可以写出时间复杂度为 $O(n)$ 和空间复杂度为 $O(n)$ 的解法：

```java
   /**
    * 309. 最佳买卖股票时机含冷冻期
    * @param prices    股票价格
    * @param k 交易最大笔数
    * @return  最大利润
    */
   public int maxProfit(int k, int[] prices) {
       if (prices == null || prices.length == 0) {return 0;}

int m = prices.length;
       int[][] dp = new int[m + 1][2];

dp[0][0] = 0;
       dp[0][1] = -prices[0];
       for (int i = 1; i < m; i++) {
           dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
           dp[i][1] = Math.max((i >= 2 ? dp[i - 2][0] : 0) - prices[i], dp[i - 1][1]);
       }

return dp[m - 1][0];
   }
   ```

### 3.6 情况六：$k$ 为正无穷但有手续费

1. 情况六对应的题目是[714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee)。
2. 由于具有相同的 $k$ 值，因此**情况六和情况二非常相似**，**不同之处在于情况六有「手续费」**，因此需要对状态转移方程进行一些修改。
3. 情况二的状态转移方程如下：

$$
   T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
   $$

$$
   T[i][k][1] = max(T[i - 1][k][0] - prices[i], T[i - 1][k][1])
   $$
4. 由于**需要对每次交易付手续费**，因此**在每次买入或卖出股票之后的收益需要扣除手续费**，**新的状态转移方程有两种表示方法**：

1. **第一种表示方法**，**在每次买入股票时扣除手续费**：

$$
      T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
      $$

$$
      T[i][k][1] = max(T[i - 1][k][0] - prices[i] - fee, T[i - 1][k][1])
      $$
   2. **第二种表示方法**，**在每次卖出股票时扣除手续费**：

$$
      T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i] - fee)
      $$

$$
      T[i][k][1] = max(T[i - 1][k][0] - prices[i], T[i - 1][k][1])
      $$
5. 根据上述状态转移方程，可以写出时间复杂度为 $O(n)$ 和空间复杂度为 $O(n)$ 的解法：

```java
   /**
    * 714. 买卖股票的最佳时机含手续费
    * @param prices    股票价格
    * @param fee   手续费
    * @return  最大利润
    */
   public int maxProfit(int[] prices, int fee) {
       if (prices == null || prices.length == 0) {return 0;}

int m = prices.length;
       int[][] dp = new int[m + 1][2];

dp[0][0] = 0;
       dp[0][1] = -prices[0];
       for (int i = 1; i < m; 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][0] - prices[i], dp[i - 1][1]);
       }

return dp[m - 1][0];
   }
   ```

## 参考文献

1. [121. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock)。
2. [122. 买卖股票的最佳时机 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii)。
3. [123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii)。
4. [188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv)。
5. [309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown)。
6. [714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee)。
7. [ 股票问题系列通解（转载翻译）](https://leetcode-cn.com/circle/article/qiAgHn)。