最优子结构

一句话理解

最优子结构：大问题最优里包含着小问题最优。

为什么要学

能 DP 的前提之一。

讲解

最短路、背包、LIS 都有。有的问题局部最优拼不出全局，那就不是 DP。

例子

最短路的前缀也是最短路。

常见错误

• 没有最优子结构硬 DP。
• 和贪心的局部最优混淆。