从力扣188（买卖股票的最佳时机IV)看动态规划

题目链接：LeetCode 188. 买卖股票的最佳时机 IV

题干：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

我想从这道题深入分析一下动态规划的特殊优势，以及假如不知道动态规划，零基础的人正常做题会遇到什么样的困境，由此得出状态转移方程的可贵性。

这道题虽然标签是困难，但属于相对简化的决策题。只有一支股票，且每次买入卖出都不能复数，也禁止了同时多笔交易。看到题目时，一个只有初步编程经验，没有经历过题海经验战术洗练的人会如何思考，有没有什么深刻的原则可以指引他走出混乱而不靠谱的想法，接近正道？

假设我只学过java，算法设计等包含套路化内容的授课未曾经历过。看到这个题目时，可以分析出的疑惑与矛盾如下：

1、我要完成多少笔交易，是越多越好吗？显然不是，因为股票一旦单调递减，零次交易是最佳的，K只是交易的上限值不是最优值。我们不可以凭借交易次数确定解的优劣。

2、怎样定义一个交易的好与坏？从单次利润来看，买入越低卖出越高结果越好，但等待高价到来的时间里我们无法进行另外的交易，这段时间的持有会让我们错过潜在的多次交易的利润，机会成本不好估量。

3、我应该以什么样的逻辑选择一定数量的交易次数？假设第二条里我们用某种方式定义出了可以综合衡量交易好坏的判断标准，我们应该先选一个综合分数最高的交易，据买出卖出日期切割左右两侧的时间片段为子区域递归迭代，得出所有解的分数后选择前小于等于K个分数为正（不亏本）的交易嘛？这是贪心算法的思想，但我们要的是全局最优解，而时间复杂度不允许我们遍历尝试所有交易决策的组合。

4、最关键的是，无论我如何决策，都很难顾及全局——牵一发而动全身，今天的选择必将影响到未来的结果，每个小点之间都在相互影响，深度耦合，很难想到如何得到理论上的最优解。

动态规划的魅力就在于它恰好擅长这类“动态”的问题，并且用状态转移方程这一变化中的不变关系作为约束，同时从下往上循环遍历的过程又让已计算的值不必重复计算，大大降低了时空复杂度。因此，如果确定部分解注定影响其他解的范围或可行性，不过于复杂的话，都可以尝试用动态规划解答。就如高中数列里部分数列可以用通项公式表达，有的数列即便递推公式十分简单，但通项公式极其复杂甚至不存在。状态转移方程就是要找出算法题目里的递推公式。

确定题目属于动态规划范围后，难点就在于如何巧妙找到合适的状态转移方程，最终求得最优解。就这道题来说，官方题解的状态可以尝试以下思路找到：在具体的代码里，状态转移方程往往是时间或逻辑上的前序状态组合生成了后序状态，因此等式左侧经常是被填充的后序状态，类似数列的a(n)=a(n-1)+a(n-2)这种逻辑。当我们循环迭代将状态数组以从前往后或其他逻辑顺序全部填充一遍后，我们手上拥有的资源便是这一系列状态点的值——【这些值必须得对最终结果有用】。如何让它对最终结果有用？最直接的方式就是让它包含最终结果的值。就如这一题的官方题解里，buy sell数组的定义都和限制条件下的最大利润有关，我们求出所有状态后，直接取最晚时间不持有股票的最大利润即可。因此，当我们不知道怎样寻找想要的状态时，可以优先看看结果想要什么——题干要最大利润，我们就定义最大利润；题干要最少天数，我们就定义最少天数。不一定是最佳或可行的状态，但至少可以有一些思路；简单来说，子结构承接最终解的目的是逻辑上合理的。

有了单个状态的定义后，剩下的问题有两个：

1、这个状态的邻域是什么

2、初始解（不是总结果的解，指的是状态变量均为基础序号的解）可以获取吗

找邻域的方式可以看决策变量——这道题每天都可以选择买或者不买，那么，当天是否持有股票就可以作为两种状态。这样看起来没有很直接，更直接的方式也可以是今天我是否购买/卖出了股票。但后者的定义只能得知当天的情况，无法包含历史决策，因此当前是否持有股票会更好。决策变量除了日期，还可以分化为交易次数【这是一个很方便用for循环遍历的变量，因此可以优先选择】。再加上常规的根据时间前后来推导状态转移方程，这道题的思路便可以基本确定了。初始解也顺其自然的可以计算出来。

因此，可以采用“判断可用动态规划解答——寻找单个状态定义——发散状态定义——寻找转移方程和初始解——迭代计算——筛选最终解”的流程处理这类题目。只要见识的多，大厂面试里应该可以较为快速上手。当然，具体编程时边界条件的处理依旧对自身素养要求较高，这点在确定思路后无论什么题型都需要多加练习。