LeetCode 股票问题的一种通用解法
LeetCode 上有 6 道关于股票买卖的问题，难度较大。本文给大家分析出一套框架，只要通过简单的变形，就能解决所有问题。
首先申明，本文介绍的只是一个种可行方案，不是最优的。这几道股票买卖题目测试数据的规模非常大，所以有几道题目按照本文介绍的方法进行提交是无法通过的，会在最后一个测试用例得到超时或超内存的错误。
虽然不能通过，我还是写了这篇文章，说明一下用意：
学习的过程分为两个阶段，先是「从 0 到 1」，然后「从 1 到 N」。你看懂一道题，只能算「从 0 到 1」，如果不能复现这种设计思路解决一类问题，那么过两天你就忘了。但是如果你能掌握一个框架，就能无限复制，举一反三，解决一大类问题。显然后者的价值更大。
读者应该能体会我的文章风格，不会单独拿出某个奇技淫巧来讲，而是尽可能成体系，就是力求给读者带来「从 1 到 N」的价值。所以我认为，既然最优解法不好理解，那么不妨先了解一套简单可行的次优解法。
本文给出的动态规划思路复杂度是 O(N^2)，经过简单变形就能处理所有问题，层层递进，可读性好。最优解法复杂度 O(N)，涉及状态机，比较难以理解，等我整理一套简单可复制的框架出来，再发篇文章详解最优解法。
以上，代表着大部分的评论内容。当大部分人还束手无策时，你已经快速写出一个次优解，这也能体现差距呀。相信本文能给你带来价值。
说了那么多废话，进入正题。
1、Best Time to Buy and Sell Stock (Easy)
动态规划详解 说过，计算机解决问题的方法就是穷举。遇到一个问题，如果想不到什么奇技淫巧，那么首先请读者自问：如何穷举这个问题的所有可能性？
这个问题的穷举很简单，我们可以这样写：
所有可能 = { 第 x 天买，第 y 天卖 }
其中 0 <= x < len(prices),
x < y < len(prices)
result = max(所有可能)我估计有的读者会开始质疑应该是开区间还是闭区间了。但是框架思维告诫我们，请暂时忽略这种细节问题，保持思路推进，等会出错的话再回来深究。现在把上述思路转化成代码：
实际上，这个解法就是可行的，能够得到正确答案。但是我们分析一下这个算法在干嘛，就能发现一些冗余计算。
如上图，可以看到大量的重复操作。我们相当于固定了买入时间 buy，然后将 buy 后面的每一天作为 sell 进行穷举，只为寻找 prices[sell] 最大的那天，因为这样prices[sell] - prices[buy] 的差价才会最大。
如果反过来想，固定卖出时间 sell，向前穷举买入时间 buy，寻找 prices[buy] 最小的那天，是不是也能达到相同的效果？是的，而且这种思路可以减少一个 for 循环。
为什么可以减少一个 for 循环呢？我举个例子你就很容易理解了。
假设你有一堆数字，你知道其中最大的数，现在从中取走一个数，你还知道最大的那个数是多少吗？不一定，如果拿走的这个数不是那个最大数，那么最大数不变；如果拿走的恰好是那个最大的数，你就得重新遍历这堆数字以寻找之前第二大的那个数，作为新的最大数。这就是我们的原始算法，每向后移动一位，就要重新遍历寻找最大值。
但是，假设你知道一堆数字中最小的那个，再添加一个新的数字，你现在是否知道最小的数字是那个？知道，只要比较一下新数和当前最小的数字，就能得到新的最小数。这就是优化算法的情况，所以可以消除嵌套循环的计算冗余。
关键不在于最大值还是最小值，而是数字的添加和减少。添加新数时，可以根据已有最值，推导出新的最值；而减少数字时，不一定能直接推出新的最值，不得不重新遍历。
很多人认为这道题不是动态规划，但是我认为最值的更新就是旧状态向新状态的转移，所以这个问题还是含有动态规划的技巧的。不要觉得此题简单，这里完成了最困难的一步：穷举。后面所有的题目都可以基于此框架扩展出来。
2、Best Time to Buy and Sell Stock II (Easy)
这道题允许多次交易，看起来比刚才的问题复杂了很多，怎么办？没有思路第一步，想想如何穷举所有可能结果。
来尝试一下吧，如果用 for 循环来穷举，会出现什么情况？
遇到这种无穷 for 循环的情况，就是使用递归的强烈暗示。我们上一题的框架只能解决一次买卖的最大收益，现在的问题是，进行一次股票卖出后，下一次应该在什么时候交易呢？这个问题和原问题具有相同结构，规模减小，典型的递归场景。只要给原框架稍加改动即可。
这道题已经做出来了，优化两步：先根据上一题消除一层循环，然后加个备忘录。优化就属于走流程，没啥可说的。之后问题的解法，都是在此代码上的简单改造。
怎么看出重叠子问题，前文 动态规划之正则表达式 有介绍，显然一个子数组切片可以通过多条递归路径得到，所以子问题一定有重叠。
但是，这样提交会得到一个内存超过限制的错误。原来有一个测试用例特别长，我们的 memo 备忘录太大了。怎么办呢，是否可以想办法减小备忘录占用的空间？答案是不可以。
动态规划详解 中对斐波那契数列的优化，就用到一个技巧直接省略了备忘录和 DP table，用 O(1) 的空间完成了计算。但是这里不适用，首先我们把斐波那契的框架抽出来：
int fib(int n) {
fib(n - 1);
fib(n - 2);
}
可以看到原问题 fib(n) 只依赖子问题 fib(n - 1) 和 fib(n - 2)，所以我们的备忘录也好，DP table 也好，一次只用记录两个子问题的答案即可。但是抽象出当前算法的框架：
def dp(start):
for sell in range(start + 1, len(prices)):
dp(sell)
显然，如果求解原问题 dp(0)，要依赖子问题 dp(1), dp(2) ... dp(len(prices) - 1)，反正数量不是个定值，所以备忘录必须开那么大，否则装不下这些依赖子问题呀！说明这就是动态规划的极限了，真的不能再优化了。
这个问题的最优解法是「贪心算法」。贪心算法是基于动态规划之上的一种特殊方法，对于某些特定问题可以比动态规划更高效。这道题用贪心很简单，就贴一下代码吧，读者应该可以很容易理解。
核心思想就是：既然可以预知未来，那么能赚一点就赚一点。
图片来自 www.leetcode.com
3、Best Time to Buy and Sell Stock III/IV(Hard)
第三题和第四题类似，就是限定了你的最大交易次数，只要解决第四题就行了，看题目：
直接套上面的框架，把这个约束 k 加进去即可：
时间复杂度 O(kN^2)，会在最后一个测试用例超时，不过好歹做出来一个可行答案，起码有 90 分吧。
4、Best Time to Buy and Sell Stock with Cooldown (Medium)
题目意思就是，你卖出之后，你的资金要冻结一天，不能第二天立即买入，至少要隔一天才能选择买入。套进框架，只要改一下子问题的参数就行了。
复杂度 O(N^2)，也会卡在最后的大规模数据，给 90 分吧。被扣了 10 分不重要，重要的是得到 90 分只花了一秒钟。
5、Best Time to Buy and Sell Stock with Transaction Fee (Medium)
每次卖出需要手续费，套进框架，把手续费从利润中减掉即可。
本文终。总结一下，我们通过最简单的两个问题，形成了一套算法模板，快速解决了剩下的困难问题。通过备忘录技巧，保持时间复杂度在 O(N^2) 级别，虽不是最优的，但也是可行的。