动态规划

动态规划的本质，是寻找状态的定义，并基于这个定义给出状态转移的方程。

最优子结构(optimal substructure）

定义

我们通常要做出一组选择来达到最优解。

在做每个选择的同事，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题的时候，动态规划通常就会很有效。其关键技术就是对每个这样的子问题都保存其解。档期重复出现时，可避免重复求解。

programming 其实是一种表格法，而非编程。分治法解决的问题是，互不相交的子问题。

最优解有两种： an optimal solution vs the optimal solution。

步骤

  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值。
  3. 计算最优解的值，通过自底向上的方法。
  4. 利用计算出的信息，构造一个最优解。

递归是自顶向下求解。
迭代可以自底向上求解。

能够用动态规划来解的问题通常具有两个性质：

  • 最有子结构性质：问题的最优解，是由相关子问题的最优解组合而成，而这些子问题可以独立求解。
  • 子问题重叠性质：最优子结构里可能出现的子问题，可能会产生重叠。

切割钢条问题

一般形式

要做基本的切割分析，得出切割方案的一般形式（因为对称性，我们总可以去掉一部分解），如：

rn = max(pn, r1 + r(n-1),…, rn-1 + r(1))

更进一步推导出具体形式：

rn = max(pn + rn-1)

递归调用树分析

借助递归调用树的节点总数，我们可以估计总调用次数。

需要通过证明，得知 T（n）= 2 的 n 次方（TODO）。

日后可以把它转化为子问题图：

动态规划的两种等价实现方法

动态规划仔细安排求解顺序，对每一个重复的子问题只求解一次，并将结果保存下来。

这是典型的时空权衡问题（time-memory trade-off）。

带备忘的自顶向下方法（top-down with memoization）。

贪心算法

与动态规划相似，贪心算法通常用于最优化问题。我们做出一组选择来达到最优解。贪心算法的四项，是每一步都追求局部最优解。

贪心选择性质的证明总是：假定一个存在一个最优解。最优解中的第一个选择如果可以被替换，替换成另一个贪心选择而能得到【另一个兼容】的最优解，则这个问题具有贪心选择性质。

只能用 dp 来解的问题，通常子问题的解是不能相容的，一个子问题的部分选择无法替换成另一个选择而让解的其他部分不变。贪心算法可以解决分数背包问题，不能解决0-1背包问题。因为0-1背包问题，把价值最高的解替换成功价值次高的解，有可能造成空间的变化，以至于让子问题的规模也得以变大-子问题的解可能也因此上升。

霍夫曼编码

霍夫曼具有贪心算法性质。
霍夫曼编码使用了一种前缀编码（prefix code），即没有任何码字是其他码字的前缀。使用这种前缀码，我们得到一串编码后可以唯一地解析出我们想要的信息，不产生二义性。

变长编码本身是一种变长编码（variable-length code），有点类似于 utf-8。核心思想是让拥有更高出现频率的 character 得到更短的码字。

摊还分析（amortized analysis）

摊还分析只能拿来分析一类特定的算法。摊还分析并不是通过分析每个操作的实际代价的界，来分析操作序列代价的界，而是直接分析序列整体的代价的界。这种方法的一个好处是，虽然某些操作的代价可能很高，但其他很多操作的代价可能很低。

Progamming Checklist

  • 先写防御性编程方案。
  • 然后写提前截断流程的子问题的答案。
  • 开始用递归或者迭代的方式求子问题的解，并逐渐推导到当前问题。