labuladong 团灭 LeetCode 股票买卖问题

NOTE: 1、作者的思路还是穷举，它使用的是基于finite state machine的方式来进行穷举的，他使用了一个三维的状态转移方程来对股票买卖问题进行统一的描述，这个三维的状态转移方程初看起来是稍微有些复杂，但是结合具体的问题后，是容易理解的。

并且作者展示了如何设计、如何实现。

2、展示了状态压缩的技巧

3、这篇文章让我想起来 finite state machine 和 dynamic programming

状态转移方程可以看做是对 finite state machine 的数学描述；

dynamic programming则告诉我们如何使用程序来进行实现；

上篇文章 LeetCode 股票问题的一种通用解法用递归的方法实现了一套简单易懂的可行解，但是时间复杂度略高，不能通过全部测试用例。

这篇文章用「状态机」的技巧给出最优解，可以全部提交通过。不要觉得这个名词高大上，文学词汇而已，实际上就是 DP table，等会儿一讲就明白了。

本文就来告诉你处理这类问题的框架，拒绝奇技淫巧，稳扎稳打，以不变应万变。

这 6 道题目是有共性的，本文通过对第四道题的分析，逐步解决所有问题。

一、穷举框架

NOTE:

一、关于本文中提及的状态、选择、base case，都是在作者的 labuladong 动态规划详解中提出的

利用「状态」进行穷举

首先，还是一样的思路：如何穷举？这里的穷举思路和上篇文章递归的思想不太一样。

而这里，我们不用**递归思想**进行**穷举**，而是利用「状态」进行穷举。

看看总共有几种「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新**状态**。看图，就是这个意思。

选择

具体到当前问题，每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。

但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后（第一次除外）。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。

NOTE:

一、必须要先buy然后sell然后再buy，它的规则有些不相交区间的意味

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

dp table 三维数组 `dp` 以及穷举框架

我们用一个三维数组 dp 就可以装下这几种状态的全部组合，用 for 循环就能完成穷举：

NOTE:

一、max(buy, sell, rest) 的含义是今天执行buy 或者今天执行sell 或者今天执行rest

二、后面的"第五题，k = 2"、"第六题，k = any integer" 都是使用的上述穷举框架

而且我们可以用自然语言描述出每一个状态的含义，比如说 dp[3][2][1]的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。很容易理解，对吧？

最终答案

我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，所能获取的最大利润。读者可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

记住如何解释「状态」，一旦你觉得哪里不好理解，把它翻译成自然语言就容易理解了。

二、状态转移框架

现在，我们完成了「状态」的穷举，我们开始思考每种「状态」有哪些「选择」，应该如何更新「状态」。

因为我们的选择是 buy, sell, rest，而这些选择是和「持有状态」相关的，所以只看「持有状态」，可以画个状态转移图。

通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程：

这个解释应该很清楚了，如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。而且注意 k 的限制，我们在选择 buy 的时候，把最大交易数 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。

现在，我们已经完成了动态规划中最困难的一步：状态转移方程。**如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。**不过还差最后一点点，就是定义 base case，即最简单的情况。

Base case

状态转移方程

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

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

三、秒杀题目

第一题，k = 1

NOTE:

LeetCode 121. 买卖股票的最佳时机简单

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

直接翻译成代码：

显然 i = 0 时 dp[i-1] 是不合法的。这是因为我们没有对 i 的 base case 进行处理。那就简单粗暴地处理一下：

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

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

第二题，k = +infinity

如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。可以这样改写框架：

NOTE:

一、上面这段话是容易产生误解的，比较容易理解的方式是: 当k = +infinity时，对应的情况是状态转移是和k无关的，是可以直接从状态转移方程中，将k维度去除，这和k=1是一致的。

其实从这个角度来看，作者在状态转移方程中添加上k这个维度其实是为了使用同一个状态转移方程来对所有的可能情况进行统一的描述，但是，这会造成理解的困难。