【113-week2】死磕动态规划3

[sadcat]

相比动态规划里两个重点里的重叠子问题来说，最优子结构是更难掌握的。

最优子结构，即一个问题的最优解包含其子问题的最优解。发掘最优子结构的过程遵循如下通用的模式：

• 证明问题最优解的第一个组成部分是做出一个选择，做出这次选择会产生一个或多个待解的子问题。

• 对于一个给定问题，在其可能得第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。

• 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。

• 利用“剪切-粘贴”技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。证明这一点是利用反证法：假定子问题的解不是其自身最优解，那么我们就可以从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去，从而得到原问题一个更有的解，这与最初的解释原问题最优解的前提假设矛盾。如果原问题的最优解包含多个子问题，通常他们都很相似，我们可以将针对一个子问题的“剪切-粘贴”论证方法稍加修改，用于其他子问题。

[JackZhangDF]

学习了。