漫画：程序教你寻找股票买入卖出的最佳时机（动态规划）

作者 | 小灰

来源 | 程序员小灰（ID：chengxuyuanxiaohui）

前一段时间，我们介绍了一个经典算法题目：寻找股票买入卖出的最佳时机。这个题目看似简单，却有着许多种变化。

在上一篇中，我们讲解了最多1次买卖和无限次买卖的解法，那么，如果只允许最多2次股票买卖，如何寻找最佳时机呢？

我们仍然以之前的数组为例：

首先，寻找到1次买卖限制下的最佳买入卖出点：

两次买卖的位置是不可能交叉的，所以我们找到第1次买卖位置后，把这一对买入卖出点以及它们中间的元素全部剔除掉：

接下来，我们按照同样的思路，再从剩下的元素中寻找第2次买卖的最佳买入卖出点：

这样一来，我们就找到了最多2次买卖情况下的最佳选择：

对于上图的这个数组，如果独立两次求解，得到的最佳买入卖出点分别是【1,9】和【6,7】，最大收益是 （9-1）+（7-6）=9：

但实际上，如果选择【1,8】和【3,9】，最大收益是（8-1）+（9-3）=13>9：

所谓动态规划，就是把复杂的问题简化成规模较小的子问题，再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解。

首先，让我们分析一下当前这个股票买卖问题，这个问题要求解的是一定天数范围内、一定交易次数限制下的最大收益。

既然限制了股票最多买卖2次，那么股票的交易可以划分为5个阶段：

没有买卖

第1次买入

第1次卖出

第2次买入

第2次卖出

我们把股票的交易阶段设为变量k（用从0到4的数值表示），把天数范围设为变量n。而我们求解的最大收益，受这两个变量影响，用函数表示如下：

最大收益 = F（n，k）（0