动态规划定义
动态规划算法是一种计算算法, 可以在多项式时间计算出问题的解
动态规划原理
动态规划的计算原理是问题分解
原理: 动态规划算法与分治法类似, 基本思想是将待求解问题分解为若干个子问题, 先求解子问题, 然后从子问题的解得到原始问题的解. 与分治法不同的是, 动态规划划分出来的子问题往往不是相互独立的. 若用分治法来解这类问题, 则分解得到的子问题数目太多, 以至于需要耗费指数时间解决问题, 而子问题的数目常常只有多项式量级. 在用分治法求解时, 有些子问题被重复计算了很多次. 如果我们能够保存已解决的子问题答案, 在需要的时候查一下, 这样就可以避免大量的重复计算, 从而得到多项式时间算法. 为了达到此目的, 可以用一个表来记录已解决的子问题答案. 不管该子问题以后是否被用到, 只要它被计算过, 就将其结果填入表中. 这就是动态规划的基本思想.
动态规划算法适用于解最优化问题.
算法的步骤如下:
- 找出最优解的性质, 并刻画其结构特征
- 递归定义最优值
- 以自底向顶的方式计算出最优值
- 根据计算最优值时得到的信息, 构造最优解
动态规划的基本要素
最优子结构
设计动态规划算法的第一步通常是刻画最优解的结构. 当问题的最优解包含了其子问题的最优解是, 称该问题具有最优子结构性质. 问题具有最优子结构性质提供了可用动态规划算法求解的重要线索.
分析问题的最优子结构性质时, 所用的方法具有普遍性, 就是反证法. 首先假设问题的最优解导出的子问题的解不是最优的, 然后再分析说明在这个假设下, 可以构造出比原有问题最优解更好的解, 从而导致矛盾.
重叠子问题
在用递归算法自顶向底解问题时, 每次产生的子问题并不总是新问题, 有些子问题被反复计算多次. 动态规划算法正是利用了这种子问题的重叠性质, 对每一个子问题只解一次, 而后将其解保存在一个表格中, 当需要再次解此子问题时, 只是以简单地查询一下. 通常, 不同的子问题个数随问题的大小呈多项式增长. 因此, 用动态规划算法通常只需要多项式时间, 从而获得较高的解题效率.
动态规划的变形
备忘录方法
备忘录方法用表格保存已解决子问题的答案, 在下次需要解此子问题时, 只要简单查看该子问题的答案, 而不必重新计算. 与动态规划算法不同的是, 备忘录方法的递归方式是自顶向底的, 而动态规划算法则是自底向顶的. 因此, 备忘录方法的控制结构与动态规划的控制结构相同, 区别在于备忘录方法为每个解过的子问题建立备忘录以备查询.
备忘录方法为每个子问题建立一个记录项, 初始化时, 该记录项存入一个特殊值, 表示该子问题尚未求解. 在求解过程中, 对每个待求的子问题, 首先查看相应的记录项. 如果存储的是特殊值, 则表示该子问题是第一次遇到, 此时计算该子问题的解并保存进记录项. 如果存储的不是特殊值, 则表示该子问题已经被计算过, 此时直接查询返回即可.
一般来讲, 当一个问题的所有子问题都至少需要解一次时, 用动态规划算法比备忘录方法好. 此时动态规划算法没有任何多余的计算. 同时, 对于许多问题, 常可利用其规则的表格存取方式, 减少动态规划算法的计算时间和空间需求. 当子问题空间中的部分字问题可不必求解时, 用备忘录方法则较有利, 因为从其控制结构可以看出, 该方法只解那些确实需要求解的子问题.