梗概
- 动态规划算法是从许多个解中尝试出最优解的算法
- 是分治法的一个特例
- 特点就是用空间换时间，把重复子问题的解保存下来，避免重复计算
- child::分治法
- 通常使用递归方法, 解空间为一个递归搜索树
- 动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。
- 子问题可以构建成多个更大的问题，我们当然是朝着目标问题的方向去构建的
- 如最小路径问题中，只往右下构建
- 子问题可以构建成多个更大的问题，我们当然是朝着目标问题的方向去构建的
注意
- 有些情况下，可能问题具有状态，不同的状态下，属于不同的问题
- 这会影响重复计算的判断
适用范围
使用条件
- 满足分治法的条件
- 计算子问题时出现重复计算
- 具有最优子结构
特点
- 动态规划搜索解空间所有解来找到最优解
- 动态规划需要回溯
- 通常具有状态