动态规划与分治方法相似,都是通过组合子问题的解来求解原问题.
动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题
动态规划方法通常用来求解最优化问题
通常按4个步骤来设计一个动态规划算法:
- 刻画一个最优解的结构特征
- 递归的定义最优解的值
- 计算最优解的值,通常采用自底向上的方法
- 利用计算出的信息构造一个最优解
最优子结构性质: 问题的最优解由相关子问题的最优解组合而成, 而这些子问题可以独立求解

钢条切割

QQ截图20210111143412.png

递归调用方法:

QQ截图20210111143551.png
QQ截图20210111144055.png
QQ截图20210111144131.png

动态规划方法求解最优钢条切割问题
- 朴素递归算法之所以效率很低,是因为它反复求解相同的子问题.
- 因此,动态规划方法仔细安排求解顺序,对每个子问题只求解一次,并将结果保存下来. 如果随后再次需要此子问题的解,只需查找保存的结果,而不必重新计算.
- 因此,动态规划方法是付出额外的内存空间来节省计算时间,是典型的时空权衡的例子.
- 而时间上的节省可能是非常巨大的: 可能将一个指数时间的解转化为一个多项式时间的解.
- 如果子问题的数量是输入规模的多项式函数,而我们可以在多项式时间内求解出每个子问题,那么动态规划方法的总运行时间就是多项式阶的.
- 动态规划有两种等价的实现方法:
  - 带备忘的自顶向下法
    - 此方法仍然按自然的递归形式编写过程,但过程会保存每个子问题的解(通常保存在一个数组或散列表中).当需要一个子问题的解时,过程首先检查是否已经保存过此解.如果是,则直接返回保存的值,从而节省了计算时间;否则按通常方式计算这个子问题.称这个递归过程是带备忘的.
  - 自底向上法
    - 这种方法一般需要恰当定义子问题”规模”的概念, 使得任何子问题的求解都只依赖于”更小的”子问题的求解.
    - 因而我们可以将子问题按规模排序,按由小至大的顺序进行求解.当求解某个子问题时,它所依赖的那些更小的子问题都已经求解完毕,结果已经保存.每个子问题只需求解一次,当我们求解它时,它的所有前提子问题都已求解完成.
  - 两种方法得到的算法具有相同的渐近运行时间,仅有的差异是在某些特殊情况下,自顶向下方法并未真正递归地考察所有可能的子问题.由于没有频繁的递归函数调用的开销,自底向下方法的时间复杂性函数通常具有更小的系数.