学习笔记

动态规划

• 暴力递归解法(自顶向下)
• 带备忘录的递归解法
• 迭代的动态规划解法(自底向上)

求解动态规划的核心问题是穷举，因为要求最值，随意必定需要穷举，但是如何高效的穷举，就是动态规划的核心价值所在。 适合使用动态规划解决的问题，在穷举方面有一些共性，就是“重叠子问题”，并且具备“最优子结构”，这样才能通过子问题的最值得到原问题的最值。那如何正确高效的穷举，还需要找到问题的“状态转移方程”，因此，动态规划的三要素为

• 重叠子问题
• 最优子结构
• 状态转移方程

状态转移方程方程是最难找到的，思维方式是需要多加训练的。