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

本文插图

本文插图

本文插图
所谓动态规划，就是把复杂的问题简化成规模较小的子问题，再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解。
首先，让我们分析一下当前这个股票买卖问题，这个问题要求解的是一定天数范围内、一定交易次数限制下的最大收益。
既然限制了股票最多买卖2次，那么股票的交易可以划分为5个阶段：
没有买卖
第1次买入
第1次卖出
第2次买入
第2次卖出
我们把股票的交易阶段设为变量k（用从0到4的数值表示），把天数范围设为变量n 。而我们求解的最大收益，受这两个变量影响，用函数表示如下：
最大收益 = F（n ， k）（0<=k<=4 ， n>=1）
既然函数和变量已经确定，接下来我们就要确定动态规划的两大要素：
1.问题的初始状态
2.问题的状态转移方程式
问题的初始状态是什么呢？我们假定交易天数的范围只限于第1天，也就是n=1的情况：

本文插图
1.如果没有买卖，也就是k=0时，最大收益显然是0 ，也就是 F（1,0）= 0
2.如果有1次买入，也就是k=1时，相当于凭空减去了第1天的股价，最大收益是负的当天股价，也就是 F（1,1）= -price[0]
3.如果有1次买出，也就是k=2时，买卖抵消（当然，这没有实际意义），最大收益是0 ，也就是 F（1,2）= 0
4.如果有2次买入，也就是k=3时，同k=1的情况， F（1,3）= 0
5.如果有2次卖出，也就是k=4时，同k=2的情况， F（1,4）= 0
确定了初始状态，我们再来看一看状态转移。假如天数范围限制从n-1天增加到n天，那么最大收益会有怎样的变化呢？

本文插图
这取决于现在处于什么阶段（是第几次买入卖出），以及对第n天股价的操作（买入、卖出或观望）。让我们对各个阶段情况进行分析：
1.假如之前没有任何买卖，而第n天仍然观望，那么最大收益仍然是0 ，即 F（n ， 0） = 0
2.假如之前没有任何买卖，而第n天进行了买入，那么最大收益是负的当天股价，即 F（n ， 1）= -price[n-1]
3.假如之前有1次买入，而第n天选择观望，那么最大收益和之前一样，即 F（n ， 1）= F（n-1 ， 1）
4.假如之前有1次买入，而第n天进行了卖出，那么最大收益是第1次买入的负收益加上当天股价，即那么 F（n ， 2）= F（n-1 ， 1）+ price[n-1]