导入

动态规划 通常用于求最优解

最优子结构规定的是子问题与原问题的关系

动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中找到最优的一个

重复子问题

重复子问题规定的是子问题与子问题的关系。

当我们在递归地寻找每个子问题的最优解的时候，有可能会会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

总结： 解决动态规划问题最难的地方有两点：

如何定义 f(n)f(n)

如何通过 f(1)f(1), f(2)f(2), … f(n - 1)f(n−1) 推导出 f(n)f(n)，即状态转移方程