从一道DP题出发，浅析DP算法的思路分析与优化方式

DP（Dynamic Programming）是一个让很多人头疼的题目类型，它的题目变化多样，没有所谓的定式，导致很多人在面对DP的时候会显得束手无措，不知道如何下手。
实际上，DP并非无迹可寻，通过总结一些DP题目，我发现，DP其实有着很多的思路可以追寻，而这些思路实际上在不同的题目上是可以共通的，通过这些思路，能大大地减轻面对DP问题时候的心里压力以及难度，这里就以一道题出发，来讲讲我总结出的一些关于DP的小技巧。

在正式进入题目之前，想讲讲我理解的DP是什么

首先，DP本质是一种思想：利用最优子状态之间的关系互相推导出别的最优子状态，所以，一个DP的题解，应该是由这几个最为重要元素构成的，而分析这个几个元素，则构成了求解DP问题的思路：
1， 状态表示
2， 状态转移
3， 初始化

基本上DP的解题就是围绕着着三个来进行的，那么我一般的DP题题解流程是这样的：
0， 发现DP
1， 寻找最优子状态与状态转移方程
2， 优化状态表示
3， 优化状态转移

第0步

其中，第0步是我认为最难的——对的，发现这是道DP其实比想出来更为困难！因为当你想明白这是道DP时，心里已经会对状态表示以及转移有底了，明白这个后，再进行一些推导和优化，就可以用一些套路一步步地逼近最优解，而没有这第0步，所有套路都无从谈起；

要解决第0步，我认为关键是，见多识广，举一反三，实际上，DP虽然千变万化，但还是有一些特点和规律的，比如说常见的博弈问题，背包问题，树上的统计问题，这些问题一般都是由DP去做的，当看到类似的问题的时候，可以直接往这个方面去考虑，这一步我认为实际上没有太多的捷径，考的更多的是见识的广度和对问题的理解程度，最重要的是，能做到举一反三，想明白每道题为什么要用DP，下次见到类似的题就能看穿本质。

从1-3步，我将结合实际的题目来展开：

第1步

题目是里口887，一道Hard题，简单描述一下就是：
你有K个鸡蛋，和一个高为N的楼，每个鸡蛋都是一样的，它能承受从某个未知的楼层X丢下而不跌破，你可以从任意楼层扔鸡蛋下去做实验，如果这个楼层大于X，则鸡蛋会摔破，否则鸡蛋完好无损，问你至少要尝试多少次才能测出X。

首先假设我们一直这道题是DP，考虑一下用什么状态来表示比较合适。显然，我们应该包含一个状态是：我们现在持有的鸡蛋数量，此外通过不同的尝试，我们可以知道X的范围，这样考虑的话，一个最简单的状态表示就出来了：f[j][k]表示经过测试，我们已知X的范围是[i,j]，并且现在剩余k个鸡蛋，问至少需要多少次试验才能知道正确的X。

得到状态表示后，状态转移实际上是一件十分机械化的事情：枚举你在这个状态下所有可以做的事情，找到里面的最优解。
[i ]所以我们再考虑，根据这个状态，我们能做什么呢——选择一个楼层，然后扔鸡蛋；对于这个题，你还需要考扔鸡蛋的结果：破了，或是没破。如果在l层破了，那么我们就知道最后结果在[l + 1, j]中，并且我们浪费了一个鸡蛋，所以答案是由f[l + 1][j][k - 1]转移过来的；如果没破，则知道最后结果在[i, l]中，并且鸡蛋数量保持不变，所以是由f[l][k]转移过来的。由于我们要考虑最坏情况，所以实际上需要的是得到一个最大值的最小值，这样的话，状态转移就已经很清楚了：

f[j][k] = 1 + min(max(f[l - 1][k - 1] , f[l][j][k])

状态数是N^2K，状态转移O(N)，最终复杂度O(N^3K)，边界条件很简单，当i=j时，我们就知道答案了。

这样，我们迈出了用DP求解这道题的第一步，也是最为关键的一步。

总结一下，我们在这一步中做了什么：

1，找到一个子状态，这个状态需要包含所有的已知信息，它可以是冗杂的，但一定要包含所有需要的信息，不要担心加入过多的状态，状态的优化交给优化步骤，在第一步中，只需要思考，如果找到一个能包含所有已知条件的状态就行了。
2，枚举在这个状态下进行的操作，得出转移方程。
3，根据状态，考虑边界条件的初始化

这一步其实没有想象中的那么困难，你只需要根据题目用尽可能丰富地信息去填充你的状态表示，然后用尽可能暴力的方式去枚举最优解找到转移方程就行了；当然，这样的步骤不一定会给你带来一个最优解，但有了这个最初的解法，就能给予我们接下来优化的基层，也有了与面试官聊下去的资本，可以说，走出这一步，已经完成了这个题目的一大半，而这一步，真的不难——最难的地方在于，你需要意识到这是一个DP；

而接下来的优化，就是根据这一步中的1和2来进行展开的。

第2步
从这一步开始，DP的解题将变得更加有迹可循。

这一步的要点是，去除状态中的冗余信息，这些冗余一般是由几个方面构成的，一般来说，从这些方面思考，就可以达成优化状态的效果。我把状态表示的优化总结为3个方向：
1. 去除非合法状态
2. 去除可推导的信息
3. 去除重复信息

我们一个个展开来说：

首先是去除不合法的状态，当我们把一个状态表示出来的时候，有时候大部分状态的结果都是0或者是不合法的，将这些不合法的状态剔除，可以大大地减少状态的复杂度，从而达到空间复杂度的降低（以及，有可能带来时间复杂度的优化）。去除不合法的状态的一个通用方法是，用记忆化搜索，这样的话，不合法的状态不会被求解，所以他们的存在不会带来时间复杂度上的提升，缺点是这样做不会降低空间复杂度；而另一种方法则不是那么通用，即观察合法的状态的规律，看看是否能根据这个合法的条件构造出新的状态，这样的话可以从空间复杂度上优化算法（有可能带来时间复杂度上的优化），比如说在这题中，如果我还记录了我已经摔碎了多少个鸡蛋，即f[j][k][l]表示我知道答案在[i,j]，手里还有k个鸡蛋，已经摔碎了l个鸡蛋的情况。那么显然这里当k+l != K的情况都是不合法的，所以可以通过这个推导出可以将l这个维度去掉；这只是一个简单的例子，实际问题还是要根据实际问题来分析，当然实在不行，直接上记忆化搜索基本不会出错。

其次是去除可推导的信息，有些状态是可以互相推导的，同样是上面的例子，我们换个角度考虑，因为我知道了k，而且有k+l = K，所以我一定可以推导出l，那么l这个维度就是冗余的，于是通过这个观察，我们可以减轻一个维度。

最后是去除重复信息，这个需要对状态内容进行考量，以这个题目来说，我们发现当k不变，j-i的值固定时，结果实际上是一样的，因为我们可以把所有[i,j]层视作[0,j-i]层！那么，根据这一点我们就可以将这个维度给抹去，得到新的状态表达：
f[k]表示剩下k个鸡蛋，范围被缩减到i层，需要的最少实验次数。
根据这个转化，可以得到新的递推方程：
f[k] = min(max(f[l - 1][k - 1], f[i - l][k]))

通过简化状态，我们将空间复杂度降低为O(NK)，时间复杂度降低为O(N^2K)

总结一下，对于状态的优化，无非从三个角度考虑：
1， 非合法状态的剔除
2， 冗余状态的剔除
3， 重复状态的剔除

第3步

最后一步，对状态转移的优化。这一步相比第二步没有那么的容易循规蹈矩，但我也总结出了一般出现的3种优化思路，足以应付大部分的状态优化：


1. 利用数据结构优化计算
2. 利用相邻状态转移的共同处进行优化
3. 利用最优解的共同处进行优化
4. 利用最优解特性进行优化


第一个思路重点是优化计算过程，实际上我并没有在刷题站上过多的看到，这里只稍作一提：
比如说，我有一个这样的递推方程f = min(a, min(f[k])), i - m <= k <= i，其中m给定，这样的方程正常递推是O(nm)级别的，但我们可以利用滑窗最小值的算法来对这个进行优化，达到O(n)的时间复杂度。


第二个思路重点是，寻找在计算中的重复信息，一个常见的题目是f  = a + sum(f[j]) i - m <= j <= i，也即，f是前m个数的和，在这里，我们在计算f与f[i-1]时，其实重复计算了sum(f[j]) i - m <= j <= i - 1这个数值，于是可以很容易线稿，通过维护一个大小为m的窗口的和，我们可以优化计算过程。


第三个思路的重点是，寻找最优解的计算过程中的性质。
回到丢鸡蛋这道题，我们发现 min(f[l - 1][k - 1], f[i - l][k])中，f[l - 1][k - 1]的结果是随着l单增的，而f[i - l][k]是随着l单减的，也就是说，如果用一个图表示，则大概是长这样的：

（没有好的画图工具，请轻喷）
阴影部分是两个中的较大值，而最优解就是箭头所指向的地方，而当k不变时，如果增加i，实际上是不会影响f[l - 1][k - 1]这个曲线的走势的，也就是说，如果将i变化对结果的影响反应在这个图上的话，就是这样的：

可以看到，当i增加时，实际上另一个直线是在向上推移的，而他与我们f[l - 1][k - 1]的交点，也就是最优解，是不断地向右推移的！


而这个推移的过程中就可以将枚举l的复杂度从O(N)变为均摊O(1)，也就是说，最后时间复杂度被优化为了O(NK)！


这题是一个很经典地四边形不等式优化的运用，而其要点就在于观察并发现最优解之间的关系，从而降低枚举最优解的复杂度。


最后一点，利用最优解特性进行优化，在枚举最优解的时候，有时候可以利用题目性质直接得出最优解的选择而优化掉枚举的过程。
这里我举一个比较有歧义但是很有意思的例子：霍夫曼树的求解。


虽然霍夫曼树在现在看起来已经是一个十分简单的堆的运用，这个算法的发现有着有趣的历史，早在这个算法被发明的时候（1951）年，这还是一个十分复杂的课题。而当时的教授Robert Fano研究霍夫曼编码的最优解算法苦苦求未果，于是把它布置成了信息论的学期报告，而霍夫曼，在苦苦思索后竟然突破了这个世界难题，得出了我们现在所熟知的基于最小堆的霍夫曼编码求解方法，也通过这个算法，在1952年发表了一篇论文。


扯远了，回到霍夫曼算法，可能你不知道，霍夫曼树的求解有一个动态规划的求解方法：霍夫曼编码的求解，等价于求一个排好序后的数的最优二叉搜索树问题，这个问题十分简单，用f[j]表示将i-j这个数合并成一颗二叉搜索树的最少代价，它的递推方程也十分简单，对于每个i，j，枚举中间的切割位置k，那么从这里切开的代价则是f[k] + f[k + 1][j]再加上sum[j]。


而现在我们也知道，可以通过贪心的策略来对这个算法进行优化，因为每次的最优策略，总是取最小的两个数合并。


总结一下这个步骤，
状态转移的优化没有那么简单，但也有一些规律或者是常用的方法可循，当你遇到瓶颈的时候，不妨从下面几个角度去考虑：
1. 利用数据结构优化转移的计算
2. 降低状态转移的计算冗余来优化
3. 寻找每个状态最优解的规律
4. 是否能在求解时利用贪心的思想优化计算

以上就是全部我在做DP过程中总结出来的思路和方法，希望能给对DP苦手的同学一些帮助和思路，选择一道Hard题作为切入点讲解也是为了希望能说明DP的思维方式实际上是有共同之处的，这些思路实际上与题目难度无关，希望能减少对DP的那种天然恐惧。

有什么不对的地方也欢迎指出和交流，码字不易，还请大家不要吝啬手中的大米，在此谢过啦~

====================================================================

最后，我这里给出一道练习题，同样是一道Hard级别的题目，我当初也做了非常的久，也是一道十分有深度的DP题目。
里口1k
提醒：这道题非常难，但如果真的能做到通过一步步优化与思考达到O(N^3)甚至O(N^2)的算法的话，一定能对自己对DP的理解有很大的提升，有时候，DP总结比刷题更加重要。

[/i]

补充内容 (2019-8-12 07:00):
emmmm，第一次用不知道怎么操作，然后发现f[j]的[i]被标识成了斜体的标签，导致整个文章变成斜体了，现在想编辑又编辑不了了，实在抱歉~[/i]

提示大家：

如果你的代码里还有  [i ]（去掉多余空格） 容易出问题。

如何解决？
发帖框里有 "<>"，这个是代码block，可以选择语言，可以完美避免 代码跟html/discuz code混乱的问题，而且UI更美观。

我的流程
0， 发现DP
1， 寻找最优子状态与状态转移方程
2,   找不到
3,   时间到 卒

刷题 发表于 2019-8-13 12:40
我的流程
0， 发现DP
1， 寻找最优子状态与状态转移方程

过度真实，引起不适。。。。

887砸蛋 当时和刷题网awice说过一个不严谨的简化做法：
丢t次蛋，最多碎K个，每次只有碎1/不碎0 两种结果。
所以总共能表示 f_K(t) = （t choose 0） + （t choose 1）+（t choose 2）+...+（t choose K）个二进制数，每个数对应1-N中的某一层楼
所以其实就是find the minimum t that f_K(t) >=N， 直接二分搜索就行了。。

emmmm，第一次用不知道怎么操作，然后发现f[i][j]的[i]被标识成了斜体的标签，导致整个文章变成斜体了，现在想编辑又编辑不了了，实在抱歉~

多谢楼主分享, 看得出楼主分析能力很不错!!!另外看不到你最后推荐的题目？

ytx2013 发表于 2019-8-13 00:34
多谢楼主分享, 看得出楼主分析能力很不错!!!另外看不到你最后推荐的题目？

就是刷题网的题号1000

多谢楼主分享，这种原创的帖子 最近真心不多了

谢谢lz的分析，开拓新的思维方式！

楼主你也太牛逼了吧 我爱你

很强，一看就是OI/ACM的教程风格