Dynamic Programming

更新中 · 笔记范围:持续补充

动态规划(Dynamic Programming)是一种算法设计方式,通常用于,问题的解是由一系列的“决定”组成的。解决的方法是分成一些子问题,把这些子问题的解存在一个表里以避免重复计算。与分治的区别是,动态规划分的子问题常常会有重叠。

一些比较抽象的使用条件:

  • 解决的问题最好有 最优子结构(Optimal Substructure): 当原问题的解是最优的时候,每个子问题的解也是最优的。
  • 子问题所占的空间较小(因为要用表格存下来)。
  • 子问题可以在多项式时间内解决。
    典型的问题结构:
    Dynamic Programming这里,例如 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}。