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

5.假如之前有1次卖出，而第n天选择观望，那么最大收益和之前一样，即 F（n ， 2）= F（n-1 ， 2）
6.假如之前有1次卖出，而第n天进行2次买入，那么最大收益是第1次卖出收益减去当天股价，即F（n ， 3）= F（n-1 ， 2） - price[n-1]
7.假如之前有2次买入，而第n天选择观望，那么最大收益和之前一样，即 F（n ， 3）= F（n-1 ， 3）
8.假如之前有2次买入，而第n天进行了卖出，那么最大收益是第2次买入收益减去当天股价，即F（n ， 4）= F（n-1 ， 3） + price[n-1]
9.假如之前有2次卖出，而第n天选择观望（也只能观望了），那么最大收益和之前一样，即 F（n ， 4）= F（n-1 ， 4）
最后，我们把情况【2 ， 3】，【4 ， 5】，【6、7】，【8 ， 9】合并，可以总结成下面的5个方程式：
F（n ， 0） = 0
F（n ， 1）= max（-price[n-1] ， F（n-1 ， 1））
F（n ， 2）= max（F（n-1 ， 1）+ price[n-1] ， F（n-1 ， 2））
F（n ， 3）= max（F（n-1 ， 2）- price[n-1] ， F（n-1 ， 3））
F（n ， 4）= max（F（n-1 ， 3）+ price[n-1] ， F（n-1 ， 4））
从后面4个方程式中，可以总结出每一个阶段最大收益和上一个阶段的关系
F（n ， k） = max（F（n-1 ， k-1）+ price[n-1] ， F（n-1 ， k））
由此我们可以得出，完整的状态转移方程式如下：

本文插图

本文插图

本文插图

本文插图

本文插图
在表格中，不同的行代表不同天数限制下的最大收益，不同的列代表不同买卖阶段的最大收益。
我们仍然利用之前例子当中的数组，以此为基础来填充表格：
首先，我们为表格填充初始状态：

本文插图
接下来，我们开始填充第2行数据。
没有买卖时，最大收益一定为0 ，因此F（2,0）的结果是0：

本文插图
根据之前的状态转移方程式， F（2,1）= max（F（1,0）-2 ， F（1,1））= max（-2 ， -1）= -1 ，所以第2行第2列的结果是-1：

本文插图
F（2,2）= max（F（1,1）+2 ， F（1,2））= max（1 ， 0）= 1 ，所以第2行第3列的结果是1：