Dynamic Programming
本页目录
动态规划(Dynamic Programming)是一种算法设计方式,通常用于,问题的解是由一系列的“决定”组成的。解决的方法是分成一些子问题,把这些子问题的解存在一个表里以避免重复计算。与分治的区别是,动态规划分的子问题常常会有重叠。
一些比较抽象的使用条件:
- 解决的问题最好有 最优子结构(Optimal Substructure): 当原问题的解是最优的时候,每个子问题的解也是最优的。
- 子问题所占的空间较小(因为要用表格存下来)。
- 子问题可以在多项式时间内解决。
典型的问题结构:
这里,例如 4 到 3 的箭头,表示规模为 4 的问题依赖于规模为 3 的问题的答案。
例子
有一段长度为整数 n 的木棍,可以不花成本地把它切成一些长度仍为整数的段。长度为 i 的段的价值为 p_{i},求切分后,最大的 每段价值之和。
- 一共有
2^{n-1}种切分方式,不可简单枚举。 - 这具有最优子结构。长度为
n的木棍,若在i处切分,最优价值就是左边长度为i的最优价值,和右边长度为n-i的最优价值加起来;也可以不切,价值为p_{n}。 - 设长度为
i的最优价值为r_{i},那么有 Bellman Equation:
r_{n}= \max \{ p_{n}, r_{i}+r_{n-i} \mid 1\leq i\leq n-1 \} - 这也等价于另一种形式,就是去枚举最左边第一刀的长度:
r_{n}= \max \{ p_{i}+r_{n-i}\mid1\leq i\leq n \} - 这里
r_{0}=0, r_{1}=p_{1}。
实现方式: - 直接递归。这样的话
T(n)=1+\sum _{i=0}^{n-1}T(i),这个结果是T(n)=\Theta(2^{n})。 - 循环,bottom-up。这样的话
T(n)=\Theta(n^{2})。 - 记忆化搜索(Memoization)。同样有
T(n)=\Theta(n^{2})。
若要得到最优的一种切分方式,可以在过程中记录一些额外的信息,例如记s_{i}表示,对于长度为i的木棒,最优的切分方式,最左边第一刀切的长度,那么取 max 过程中就可以得到这个s_{i}。