# 第 6 节最优子结构、重复子问题、无后效性

# 最优子结构

即，较小规模的子问题的可以构成较大规模的子问题。这部分和「状态转移方程」一样去理解就好。

由于有很多重复子问题，所以子问题的结果需要记录下来。

学习「动态规划」，一定须要深刻理解「无后效性」。「无后效性」这个概念超级超级重要。

很遗憾，在《算法导论》里都没有找到关于「无后效性」的解释。在李煜东的《算法竞赛进阶指南》里是这样描述「无后效性」的：

提示：动态规划要求已经求解的子问题不受后续阶段的影响。

这句话我根据经验总结如下：动态规划在解决子问题的过程中，一旦某一个子问题的求解结果确定以后，就不会再被修改。重要的事情说 3 遍：求解的过程形成了一张 有向无环图，求解的过程形成了一张 有向无环图，求解的过程形成了一张 有向无环图。

因此，子问题的定义就非常关键。常见的做法是：在设计状态的时候，维度定得细一点，通常表现为增加维度。这样一来，新的子问题就可以比较容易参考以前计算出来的子问题的结果，以避免复杂的分类讨论。

无后效性这个概念一开始不理解没有关系，理解它需要我们有一些求解问题的经验。一边解决问题，一边理解概念。

作者：liweiwei1419 链接：https://suanfa8.com/dynamic-programming/optimal-substructure 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。