这篇能让你搞懂股票买卖系列问题

客官°小女子只卖身不卖艺 2023-07-21 08:46 18阅读 0赞

## 写在前面 ##

**如果觉得写的还不错，有所收获，记得点个关注和点个赞哟，不胜感激。**  
股票买卖的这个系列问题早在之前就在LeetCode就刷了一遍了，不过当时因为一些原因，没有总结成一篇博文。后面又陆陆续续遇到了类似的问题，总感觉股票系列问题的奇技淫巧太多了，平时用来学习和拓展完全是没有问题的，不过如果到了一些正式场合，一般不会想到那些巧妙的办法，怎么办呢？所以这一篇博文就打算稳扎稳打，通过较为详细的讲解，用一种通用方法解决所用问题，以不变应万变。

### 文章目录 ###

*   *  写在前面
     *  相关问题引入
     *  理解状态是什么
     *  状态转移框架
     *  实战解决问题
     *   *  当只能进行一次交易时
         *  当可以进行无穷多次交易时
         *  当可以交易无穷多次，且限制暂停交易
         *  当可以进行无穷多次交易，且需要付手续费
         *  当可以进行两次交易时
         *  当可以进行任意次交易

## 相关问题引入 ##

股票买卖问题都已经是老生常谈的问题了，不过按照正常逻辑，还是要说明一下问题的，不然可能对于一些尚且不知道的读者来说不友好，所以这里还是将相关的问题地址贴出来，就不在博文里描述问题了，如下：

[买卖股票的最佳时机][Link 1]  
[买卖股票的最佳时机 II][II]  
[买卖股票的最佳时机 III][III]  
[买卖股票的最佳时机 IV][IV]  
[最佳买卖股票时机含冷冻期][Link 2]  
[买卖股票的最佳时机含手续费][Link 3]

值得一提的是，对于每个问题，都有一些出色的文章解释如何解决对应问题。但是，大多数解答都无法确定这些问题之间的联系，因此很难找到一种一致的方式来处理这一系列问题。在这篇博文中，我将介绍适用于所有这些问题的最通用的解决方案，并将其专门化为上述六个问题中的每一个。

这篇文章将会通过状态机来讲解，可能很多人一听见状态机，就心生敬畏，觉得这是一个遥不可及的东西，其实不用觉得有多高大上，实际上就是 DP table，等你理解了你就能明白了，后面我想着专门写一篇文章来讲状态机思路的一些独特用法，因为也碰到了一些问题，可以通过状态机完美解决。正式开始之前呢，我们先看看一段代码

int maxProfit(vector<int>& prices) { 
        if(prices.empty()) return 0;
        int s1=-prices[0],s2=INT_MIN,s3=INT_MIN,s4=INT_MIN;
            
        for(int i=1;i<prices.size();++i) {             
            s1 = max(s1, -prices[i]);
            s2 = max(s2, s1+prices[i]);
            s3 = max(s3, s2-prices[i]);
            s4 = max(s4, s3+prices[i]);
        }
        return max(0,s4);
    }

这段代码很精简，看起来没几分钟就看完了，不过很多时候，越精简的代码，往往越有奥妙，值得深入研究。当然上面的这段代码就是解决其中一个股票问题的代码，很简单吧，不过如果你觉得你已经明白了其中的奥义，可以干掉所有股票问题的代码的时候，你可以尝试把上面六个问题都自己写一遍，我相信你还会回来的。如果你还没飘，请继续看下去。别看别人一下子能写出这么牛逼精简的代码，开始怀疑自己，其实这类问题是有框架的，一旦你搞明白了框架，你也可以写出这样的代码。所以这里还是要说个题外话，就是如果自己还很菜的话，就多刷题，多看，多研究，把套路摸清楚之后，你在那些还不懂套路的小白面前，就是大佬。

言归正传，这 6 道股票买卖问题是有共性的，我们通过对第四题（限制最大交易次数为 k）的分析一道一道解决。因为第四题是一个最泛化的形式，其他的问题都是这个形式的简化或者衍生。第一题是只进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = +infinity（正无穷）；第三题是只进行 2 次交易，相当于 k = 2；剩下两道也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理。

## 理解状态是什么 ##

首先，我们来点简单暴力的，就是穷举，不过这里要说的穷举，不是像递归或者普通的多层遍历之类的那种，对所有买卖组合进行穷举。我们来点不一样的思路，另辟蹊径。在这里，我们部队所有的买卖组合进行穷举，而是对每一天的`「状态」`进行穷举。可能比较难理解，具体一点说，就是我们具体到每一天，看看总共有几种可能的`「状态」`，再找出每个`「状态」`对应的`「选择」`。我们要穷举所有`「状态」`，穷举的目的是根据对应的`「选择」`更新状态。听起来抽象，你只要记住`「状态」`和`「选择」`两个词就行，下面实操一下就很容易明白了。我们将这种思路简单的代码化一下，如下：

for 状态1 in 状态1的所有取值：
        for 状态2 in 状态2的所有取值：
            for ...
                dp[状态1][状态2][...] = 择优(选择1，选择2...)

比如说这个问题，每天都有三种`「选择」`：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。

很复杂对吧，不要怕，我们现在的目的只是穷举，它有再多的状态，我们要做的就是一把梭全部列举出来。这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

dp[i][k][0 or 1]
    0 <= i <= n-1, 1 <= k <= K
    n 为天数，大 K 为最多交易数
    此问题共 n × K × 2 种状态，全部穷举就能搞定。
    
    for 0 <= i < n:
        for 1 <= k <= K:
            for s in { 0, 1}:
                dp[i][k][s] = max(buy, sell, rest)

而且我们可以用自然语言描述出每一个状态的含义，比如说 `dp[3][2][1]` 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 `dp[2][3][0]` 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。我们想求的最终答案是 `dp[n - 1][K][0]`，即最后一天，最多允许 K 次交易，最多获得多少利润。这个时候你可能问为什么不是 `dp[n - 1][K][1]`？因为 `[1]` 代表手上还持有股票，`[0]` 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。到这里，你需要记住如何解释`「状态」`，一旦你觉得哪里不好理解，把它翻译成自然语言就容易理解了。

## 状态转移框架 ##

现在，我们完成了`「状态」`的穷举，我们开始思考每种`「状态」`有哪些`「选择」`，应该如何更新`「状态」`。只看`「持有状态」`，可以画个状态转移图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]  
通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
                  max(   选择 rest  ,           选择 sell      )
    
    解释：今天我没有持有股票，有两种可能：
    要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
    要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
    
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
                  max(   选择 rest  ,           选择 buy         )
    
    解释：今天我持有着股票，有两种可能：
    要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
    要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

这个解释应该很清楚了，如果 buy，就要从利润中减去 prices\[i\]，如果 sell，就要给利润增加 `prices[i]`。今天的最大利润就是这两种可能选择中较大的那个。而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。现在，我们已经完成了动态规划中最困难的一步：状态转移方程。如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。不过还差最后一点点，就是定义 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
    解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

把上面的状态转移方程总结一下：

base case：
    dp[-1][k][0] = dp[i][0][0] = 0
    dp[-1][k][1] = dp[i][0][1] = -infinity
    
    状态转移方程：
    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])

这个时候你可能会问，这个数组索引是 -1 怎么编程表示出来呢，负无穷怎么表示呢？这都是细节问题，有很多方法实现。现在完整的框架已经完成，下面开始具体化。

## 实战解决问题 ##

### 当只能进行一次交易时 ###

直接套状态转移方程，根据 base case，可以做一些化简：

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 = 0 的 base case，所以 dp[i-1][0][0] = 0。
    
    现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
    可以进行进一步化简去掉所有 k：
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    dp[i][1] = max(dp[i-1][1], -prices[i])

转换成代码如下：

int n = prices.length;
    int[][] dp = new int[n][2];
    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]);
    }
    return dp[n - 1][0];

显然 `i = 0` 时 `dp[i-1]` 是不合法的。这是因为我们没有对 `i` 的 base case 进行处理。可以这样处理：

for (int i = 0; i < n; i++) { 
        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]
            continue;
        }
        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];

`k = 1`的情况就这样解决了，但是这样处理 base case 很麻烦，而且注意一下状态转移方程，新状态只和相邻的一个状态有关，其实不用整个 dp 数组，只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1):

int maxProfit_k_1(int[] prices) { 
        int n = prices.length;
        // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) { 
            // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            // dp[i][1] = max(dp[i-1][1], -prices[i])
            dp_i_1 = Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }

两种方式都是一样的，不过这种编程方法简洁很多。但是如果没有前面状态转移方程的引导，是肯定看不懂的。后续的题目，我主要写这种空间复杂度 O(1) 的解法。

### 当可以进行无穷多次交易时 ###

如果 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])
    
    我们发现数组中的 k 已经不会改变了，也就是说不需要记录 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])

直接翻译成代码：

int maxProfit_k_inf(int[] prices) { 
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) { 
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

### 当可以交易无穷多次，且限制暂停交易 ###

每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
    解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。

翻译成代码：

int maxProfit_with_cool(int[] prices) { 
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        int dp_pre_0 = 0; // 代表 dp[i-2][0]
        for (int i = 0; i < n; i++) { 
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp;
        }
        return dp_i_0;
    }

### 当可以进行无穷多次交易，且需要付手续费 ###

每次交易要支付手续费，只要把手续费从利润中减去即可。改写方程：

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] - fee)
    解释：相当于买入股票的价格升高了。
    在第一个式子里减也是一样的，相当于卖出股票的价格减小了。

直接翻译成代码：

int maxProfit_with_fee(int[] prices, int fee) { 
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) { 
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
        }
        return dp_i_0;
    }

### 当可以进行两次交易时 ###

`k = 2` 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大。要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也没有存在感。这道题 k = 2 和后面要讲的 k 是任意正整数的情况中，对 k 的处理就凸显出来了。我们直接写代码，边写边分析原因。

原始的动态转移方程，没有可化简的地方
    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])

按照之前的代码，我们可能想当然这样写代码（错误的）：

int k = 2;
    int[][][] dp = new int[n][k + 1][2];
    for (int i = 0; i < n; i++)
        if (i - 1 == -1) {  /* 处理一下 base case*/ }
        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][k][0];

为什么错误？我这不是照着状态转移方程写的吗？还记得前面总结的「穷举框架」吗？就是说我们必须穷举所有状态。其实我们之前的解法，都在穷举所有状态，只是之前的题目中 k 都被化简掉了。这道题由于没有消掉 k 的影响，所以必须要对 k 进行穷举：

int max_k = 2;
    int[][][] dp = new int[n][max_k + 1][2];
    for (int i = 0; i < n; i++) { 
        for (int k = max_k; k >= 1; k--) { 
            if (i - 1 == -1) {  /*处理 base case */ }
            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]);
        }
    }
    // 穷举了 n × max_k × 2 个状态，正确。
    return dp[n - 1][max_k][0];

如果你不理解，可以返回第一点「穷举框架」重新阅读体会一下。这里 k 取值范围比较小，所以可以不用 for 循环，直接把 k = 1 和 2 的情况手动列举出来也可以：

dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
    dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
    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], -prices[i])
    
    int maxProfit_k_2(int[] prices) { 
        int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
        int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
        for (int price : prices) { 
            dp_i20 = Math.max(dp_i20, dp_i21 + price);
            dp_i21 = Math.max(dp_i21, dp_i10 - price);
            dp_i10 = Math.max(dp_i10, dp_i11 + price);
            dp_i11 = Math.max(dp_i11, -price);
        }
        return dp_i20;
    }

有状态转移方程和含义明确的变量名指导，相信你很容易看懂。其实我们可以故弄玄虚，把上述四个变量换成 a, b, c, d。这样当别人看到你的代码时就会一头雾水，大惊失色，不得不对你肃然起敬。

### 当可以进行任意次交易 ###

有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了。现在想想，交易次数 k 最多有多大呢？一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 `n/2`，如果超过，就没有约束作用了，相当于 `k = +infinity`。这种情况是之前解决过的。直接把之前的代码重用：

int maxProfit_k_any(int max_k, int[] prices) { 
        int n = prices.length;
        if (max_k > n / 2) 
            return maxProfit_k_inf(prices);
    
        int[][][] dp = new int[n][max_k + 1][2];
        for (int i = 0; i < n; i++) 
            for (int k = max_k; k >= 1; k--) { 
                if (i - 1 == -1) {  /* 处理 base case */ }
                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]);     
            }
        return dp[n - 1][max_k][0];
    }

[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
[II]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
[III]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
[IV]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
[Link 2]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
[Link 3]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/6c623dcd0c344c13b385f4608469057a.png