第六周学习笔记

动态规划

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）

共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解

关键点

1.最优子结构
2.定义状态空间
3.DP方程