知道有“最优性原理”并不代表你就能看出问题的最优性原理。因为知道这个词，不代表你就能直观地理解这个词。对于正常的NOIPer或者IOer，理解这个词的方法就是做题，不停地做题，反复地去做题。直到做过了所有常见的题型，然后等着一朝顿悟。但是我却不行——我经常会把搜索题当作动规题去做，而当时还没有一个所谓“DP练习题库”这么一种东西。

那么混着练？饶了我吧。

其实真正不清楚的是一个最基础的东西：问题空间。

我已经忘了我是什么时候领悟这个概念的。问题空间，说起来好牛逼，感觉好玄乎。

如果在你的头脑里面，你对一个问题，想到了这么一种“可操作的”方案，可以通过一个一个地检查候选答案的方式去解决问题。那么我们说这个问题的问题空间是线性的；如果你需要深入一种情况，处理完毕，然后回来处理其他的情况，我们说这个问题空间是树状的；如果你需要发现面对的情况不止是可能改变你现在手上掌握的信息，还可能会改变你曾经面对过的情况，那么我们说这个问题空间是图状的。

我可以这样举个例子来理解：假设你要捉小偷，到十个房间去找小偷。那么，你可以一间房子一间房子地去找，因此问题空间是线性的；如果房间里面分小房间，而我们没法一眼就判断小偷在不在这个房间里，那么问题空间就是树状的；而如果小偷会穿墙，或者房间之间是互相连通的，那么问题空间就是图状的……

很显然，在第一种情况下捉到小偷最容易，在最后一种情况下捉到小偷最难，甚至永远都捉不到。

我最开始实际上是被“问题空间”这样的名字给迷惑住了——当然它还有好多个称呼，比如“解空间”，“问题抽象”，等等——恩，如果我搞错了概念，可千万别骂我，我是ACMer渣渣。我一直以为问题空间是指的问题本身的某种结构——这个理解当然没错，只是掉了几个字。问题空间是指的“在你眼中”的问题本身的某种结构…………

选择性失明害死人啊……

找到了问题的结构，本质上就是在对问题进行数学建模。在寻找一种解决问题的具体方案。也许这就是为什么我当初没有领悟这个概念的原因吧：因为领悟这个概念的唯一办法，可能就只有经验的积累——我现在把这个概念说的非常明白了，但是你能不能一眼从问题中看到其中蕴含着的结构呢？不能吧？

那么回到头来，所谓的“动态规划”的“最优性原理”（也叫“最优性子结构”）的含义就是，在你理解的问题结构中，问题可以被分解为几个不同的部分，这个问题的解答是最优的，当且仅当被分解的每个部分的解答都是最优的，也就是说不存在这么一种情况，我将问题划分成三个部分然后求解，但是，整个问题的最优解中，子问题三的对应解答不是最优的。这就好像你的问题模型里面有“岔道”，当你解决一个问题的时候，你不一定从正道走，甚至有时候是一定不能从正道去走，这样的问题就是没法动态规划的。必须保证问题在解答上是“静态”的，才能用动态规划去解决。

而所谓的“无后效性”则简单多了，就是你做出的每次选择，都不会改变你之前做过的决定。比如说，有小偷在十个房间里，而这十个房间互不连通，而且小偷不会穿墙术。

那么当你检查完一号房间以后，你确认小偷不在里面，那么在之后所有的步骤中，你都能确认小偷不会再出现在一号房间，直到最后找到小偷。

那么，显然地，最麻烦的事情不是理解这些概念，而是如何在问题中发现这些概念。如何敏锐地找到这些问题内部所固有的结构，这就是最关键的。而这，显然是需要大量的做题，大量的经验的。这是完全跑不掉的。

最近在网上看到吐槽，说人生如何能动态规划。显然人生不满足最优性原理：你就算在每个时刻都做出正确的决定，最终也可能是不幸福的人生。而人生也不满足无后效性：

你有可能会后悔你做出的那个决定，哪怕在当时，这个结论是五笔正确的。而且可能最麻烦的：你未来的一个正确选择，会显示出你过去那个正确选择，是多么的愚蠢。

    （未完待续）