动态规划与排列组合

1、像所有的新手一样，对一种算法思想的理解需要经历从肤浅（流于表 面形式）到逐渐触摸到本质的过程。为什么说，逐渐触摸到本质，是 因为很多时候你并不确定一个解释是不是最本质的，有时候会有好几 个等价的解释，各自在不同的场景下具有启发。比如对动态规划（DP）的理解，一开始我理解为递推，但实际上这 是最肤浅的理解，对于如何在特定的问题中找到递推关系毫无帮助和 启发。换言之，这只是一个描述性的总结，而不是一个建设性的总结， 不含方法论。做（看）了一些题日之后我开始总结关丁How的方法，怎样寻找到 递推关系（递推关系蕴含着子问题）。得到一个简单的观察，如果一 个问题里面含有n这个变量，考虑把n变成n- 1的

2、情况。当然，这个方法是非常特殊（狭窄）的。实际上更具一般性的方法是 不仅可以从n-1后面切一刀，还可以在任意地方切（譬如切成两个n/2 规模的），以任意标准切（比如像快排那样的】所有考虑各种切法中 哪种能够最有利于建立子问题是有帮助的。这个我姑且把它叫做通过直接切分问题来寻找子问题。可是。这还是特殊了。因为显然这个方法不能解决所有的DP问题， 连多数DP问题都未必能解决。譬如大家熟悉的最大（小）和连续 子序列问题，就难以通过这种方法求解（可行，但思维难度较大 再譬如上次Lee给的敲石头问题，以及DD出的不听话的机器人问题。因此，在知道了这几个问题的解法之后我继续思考这些解法里面是不是蕴含着更具

3、一般性的解题方法。看起来我找到了一个，就是分类讨论法，具体做法是：首先，写出可 行解的一般形式，譬如a1, a2, ., an。然后对其中的某个不确定的ai 进行讨论。譬如旅行商问题里面对下一个城市进行讨论。当不确定 时，讨论。讨论的每个分支都带来了进一步的确定性，从而将问题转 化成一个子问题。然后Lee提到，这个方法是自顶向下的，有时候不适于思考，譬如对 敲石头问题。并提到一种自底向上，着重于构造状态的外推法。于是，到日前为止，DP的一般性启发式思考方法就已经有了三种：通过直接对问题切分来探索子问题。通过对可行解的分类讨论来探索子问题。通过建立状态来自底向上地推导最终解。可是，我心里还是不踏

4、实，因为离散的知识是极其不利于记忆的， 需要更多的练习才能在运用的时候不由自主的联想起来，而且也容 易遗忘。每次做DP题的时候，我都得把好几种指导性的思路一一费 劲从脑袋里翻出来，然后尝试。实在很不爽。虽然DP题也许并没有 万用的解题手法，但我还是希望能够尽量提取出不同手法之间的本质 联系，如果能够将一组看上去离散的知识点统一在一个更具一般性， 更本质的知识点下面，我们的知识树就多出了一个根节点，于是下次 提取的时候只要提取出那个根节点，下面的几个子节点就会一一乖乖 闪现，极大的降低记忆的复杂性。那么，上面三种手法的本质联系到底是什么呢？有一次在路上走的时候我想出了一种解释。它也许不是最本质的

5、，也许大牛们早就想到过，但是我觉得至少有两个好处：它涵盖以上三种手法，通过增加一个根节点，减少知识的记忆复 杂性和易提取性。归纳抽象的过程本身就是一种锻炼，锻炼的是归纳抽象的能力。这个解释就是：大多DP问题的可行解的形式是一个排列组合（典型 的一一旅行商问题、最短路径问题）。大家都知道，穷举一个规模为 N的排列组合复杂性是aAn的，也就是”组合复杂性。而求解DP问题 的核心步骤：发现“子问题”，这个“子问题”实际上就是对应最终 解的那个排列组合的某个子排列组合（某种子集）；而这里的“子 排列组合的数目则往往是多项式的（silwile，XuYou，g9指出并非 总是如此），这就是为什么一个组合复

6、杂性的穷举问题可以DP优化为 多项式复杂度的问题。将重复出现的子排列组合对应的子问题的解缓 存起来，就是DP的缓存优化了。此外，这一解释也提供了如何探索子问题的一个通用方案：寻找形式 相同的子排列组合。还是拿最大和连续子序列说事，其解的形式是： Ai, Ai+1, ., Aj-1, Aj，其中i,j不确定。那么如何得到形式相同的子 组合呢？首先讨论Aj，为什么要讨论，因为只要入日不确定，Aj-1 就不确定，就拿不出子组合来。对于一个确定的Aj0，解的可能性为 Ai, Ai+1, ., Aj0-1, Aj0。其最优解依赖于子组合Ai, Ai+1,., Aj0-1，到这里子问题就不请子现了： Ai, Ai+1, ., Aj0-1, Aj0和 Ai, Ai+1, ., Aj0-1的形式相同，意味着它们是同一个问题的不同阶 表示。当然，由于这个指导思想一般性大了点，所以实际问题中往往没有前 面提到的三种手法寻找方案来得快众所周知的是，越特定的手法 解题面虽然越窄，但如果题日对口了解决起来也越快。但它至少有两 个好处（前面说过了）。所以考虑一般性和特殊性的手法都是有帮助 的。类似的，敲石头问题也可以通过这种手法来探索子问题。至少日前我 做过的DP题似乎都可以借助这种手法来探索，当然，刚才说过了， 未必是