Dynamic Programming

动态规划

什么是 DP？

DP 是一种算法设计思路，它有两个主要特点：

• 用低复杂度（polynomial）的方法解决看似高复杂度（看似 exponential）的问题

• 常常可以用于优化问题（min/max），如最短路径

通常 DP 的手段是递归（recursion）和记忆（memoization），通过将问题递归地拆分成子问题，找到相同子问题，复用结果来降低问题的复杂度，所以它又可以理解成：

• careful brute force

• recursion + "re-use"

接下来我们通过几个例子来领会 DP 精神：

• Fibonacci numbers

• Shortest Paths

Fibonacci Numbers

斐波那契数列定义如下:

$$F_1 = F_2 = 1; F_n = F_{n-1} + F_{n-2}$$

如果我们要求第 n 个斐波那契数字，会如何做？

我们很容易想到一种暴力解法，而且代码写起来非常好看：

fibonacci_brute_force.py

def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

我们可以画一下该解法的递归树：

recursion tree of brute force approach to nth fibonacci number

通过一系列数学推导，可以得到这种解法的复杂度为 $O(2^{\frac{n}{2}})$ ：

$$T(n) = T(n-1) + T(n-2) + O(1) \geq 2T(n-2) + O(1) \geq O(2^{\frac{n}{2}})$$

但从递归树上不难观察到，很多节点的计算是重复的，因此如果我们能够只对重复节点计算一次，问题的复杂度就降下来了，于是就有以下解法：

fibonacci_dp.py

def fib(n):
    if n <= 2:
        return n
    memo = {1: 1, 2: 1}
    for i in range(3, n+1):
        memo[i] = memo[i-2] + memo[i-1]
    return memo[n]

以上解法充分体现了，通过 memoization 来复用重复计算的结果，降低计算复杂度的思想，每个子问题的复杂度为 $O(1)$ ，因此整体复杂度为 $O(n)$ 。

通过观察我们可以发现，其实在计算过程中，每次只用到了之前两个斐波那契数，因此我们可以将记忆空间进一步缩小到 2：

fibonacci_dp_optimized.py

def fib(n):
    if n <= 2:
        return n
    na, nb = 1, 1
    for i in range(3, n+1):
        na, nb = nb, na+nb
    return nb

总结一下：

在 Fibonacci numbers 的例子中，我们通过观察递归树，找到重复计算节点，并进一步将计算过程转化为 DAG，理清不同子问题之间的依赖关系，按照依赖关系依次从小到大地解决子问题，同时通过 memoization 避免重复计算，从而最终解决原问题。

Shortest Paths

问题描述：找到图中，节点 s 与 v 之间的最短路径 $\delta(s, v)$ ，即 single-pair-shortest-path problem (SSSP)

同样可以从暴力思路开始，假设 $\delta(s, v)$ 如下图所示：

从最后一条边 $(u,v)$ 开始，假设能够到达 $v$的节点有多个， $u_1, u_2, u_3, ... u_n$ ，假设我们已经知道了 $\delta(s, u_i), i = 1, 2, ..., n$ ，那么可以得到：

$$\delta(s, v) = \min_{i}{(\delta(u_i, v) + w(u_i, v))}$$

接着依次去递归 $\delta(u_i, v)$ ，在 base case $\delta(s, s) = 0$ 作用下，得到结果。可以想象，暴力思路的递归树呈现指数增长，这并不是一个高效的方法。但需要注意的是，这里暂时只考虑有向无环图的情形，后续会介绍在存在环、存在负权重环的情形下如何解决 SSSP。

有了 Recursion，减少重复计算的方法就是 Memoization，只要记住计算过程中所有的 $\delta(s, v), v \in V$ 即可。这种解法的复杂度为：

$$time = \sum_{v \in V}{indegree(v) + 1} = O(V+E)$$

注：这里的常数 1 指的是考虑到有可能出现没有 indegree 的节点。

如果图中存在环，怎么办？

可以把图转化成多层，每层都含有图中的所有节点，每次只能访问下一层的节点，如下图所示：

这样就成功地将有环图转化成了 DAG，达到降维攻击的目的。原问题就转化为：

$$\delta_{k}(s, v) = \delta(s, v) \ with \leq k \ edges$$

k 取多少，即 DAG 有多少层合适？答案就是 $|V|$ ，理由与 Bellmand-Ford 如出一辙，且实际上这就是 Bellmand-Ford。分析它的递归树，可以知道，整个递归过程共有 $|V|^2$ 个子问题，且每个子问题消耗的时间为 $O(V)$ ，粗略计算复杂度为 $O(V^3)$ ，但仔细思考，同暴力解分析中的 indegree 求和过程，更精确的算法复杂度为：

$$time = \theta(V \sum_{v \in V} indegree(V)) = \theta (VE)$$

总结一下，本节用 DP 的思想分析 SSSP，得到了类似的答案，这也证明了 DP 作为算法设计思想的魅力。

DP 设计的 5 个步骤

1. define subproblems

2. guess (part of solution)

3. relate subproblem solutions

4. recurse + memoize/build DP table bottom-up check computation graph is acyclic, and think about topological order

5. solve original problem

以前两个例子为例：

Steps/Examples	Fibonacci	Shortest Paths (with cycle)
1	$F_k$ for $1 \leq k \leq n$	$\delta_{k}(s, v)$ for $v \in V$ , $0 \leq k \lt |V|$ = min s-> v path using $\leq$ k edges
2	no need to guess	edge into v (if any)
3	$F_k = F_{k-1} + F_{k-2}$	$\delta_{k}(s, v) = min \{ \delta_{k-1}(s, u) + w(u, v) | (u, v) \in E \}$
4	for $k = 1, ..., n$	for $k = 0, 1, ..., |V|-1$ for $v \in V$
5	$F_n$	$\delta_{|V|-1}(s, v)$ for $a = b$

根据这 5 个步骤，再看一个例子：

• Text Justification

Text Justification

text justification 要解决的问题就是如何将一段文字放入一个固定宽度的文本框中，使得文字整体感觉更美观。它的实际应用很常见，比如 Microsoft Office Word，LaTeX 等。在早期的版本中，Microsoft Office Word 使用的是贪心算法，在每一行放入尽可能多的文字，因此就经常会出现下图中的排版：

Greedy Approach to Text Justification

但通过将第一行的 blah 移到第二行，我们可以获得一个更美观的排版，如下图所示：

Dynamic Programming Approach to Text Justification

首先，为了表示美观，我们提出一个 badness 函数：

• 如果本行所有单词及其间空格总长度大于文本框宽度： $badness(i, j) = \infty$

• 如果本行所有单词及其间空格总长度小于文本框宽度： $badness(i, j) = (w_{page} - w_{words})^3$

那么 text justification 目的就是找到合适的排版方式使得 $\sum {badness}$ 最小。

Define Subproblems

为 words[i:] 找到最小的 $\sum {badness}$ 划分，subproblems 的数量为 $\theta(n)$ ，这里的 $n$ 表示单词的数量

Guessing

以哪个单词作为本行的结尾，共有 $O(n)$ 种可能

Recurrence

$DP[i] = min_{j}{(badness(i, j) + DP[j])}, j \in [i+1, n+1]$ ，且 $DP[n] = 0$ ，每个子问题的时间复杂度为 $\theta(n)$

Order

根据计算图可以发现，从 DP[n] 倒着计算到 DP[0] 是符合拓扑排序的，因此也可以算出总体的时间复杂度为 $\theta(n^2)$

Solution

DP[0]

Parent Pointers

实际上 DP[0] 并不是我们需要的结果，而是具体的换行位置，为了从 DP[0] 中得到换行位置，我们需要在计算过程中利用 parent pointers 来记录求解的路径，这也是利用 DP 求解各种类型问题后获取求解路径的惯用做法。

序列问题中 subproblems 的结构

• suffixes： $x[i:]$

  • text justification

  • knapsack (more than just suffixes)

• prefixes： $x[:i]$

• sub-sequences： $x[i:j]$

  • edit distance

本节使用 DP 解决 3 个新问题：

• Parenthesization

• Edit Distance

• Knapsack

Parenthesization

在矩阵乘法中，虽然没有交换律，但有结合律，因此在计算 $A[0] \cdot A[1] \cdot ... \cdot A[n-1]$ 时，总是存在一种最优的计算顺序，这种计算顺序可以使用加括号来表示，因此这个问题被称为 parenthesization，如下图所示：

parenthesization

Subproblems/Guessing

这是一个典型的序列问题，因此要么从第一次矩阵相乘开始思考，要么从最后一次矩阵相乘开始思考，显然，这里从最后一次矩阵相乘开始思考更符合逻辑。最后一次矩阵乘法一定是将整个序列分成两部分，如果两部分各自的最优计算顺序，也就不难算出最后一次矩阵乘法的最优计算顺序：

$$A[0] \cdot A[1] \cdot ... \cdot A[n-1] = (A[0] \cdot A[1] \cdot ... \cdot A[k-1]) \cdot (A[k] \cdot A[k+1] \cdot ... \cdot A[n-1])$$

对号入座，发现本问题的 subproblems 结构是 sub-sequences 形式，即 $X[i:j]$

Recurrence

$DP[i, j] = \min_{k}(DP[i, k] + DP[k, j] + cost), k = i+1, ..., j$

$DP[i, i+1] = 0$

cost/subproblem = $\theta(j-i)$ = $O(n)$

Topological order

以 subsequence 的距离，从小到大

Original Problem

$DP[0, n]$ ，最后使用 parent pointers 来构建最优解路径

Edit Distance

给定两个字符串 x & y，计算它们之间的最小编辑距离。这里的编辑包括 insert，delete 以及 replace，三者操作的成本不同。它的应用范围包括：

• DNA comparison

• Diff

• CVS/SVN/GIT

• Spellchecking

• Plagiarism Detection

• etc

如果 insert 和 delete 的 cost 都为 1，replace 的 cost 为 ∞，那么最小 edit distance 就等价于 longest common subsequence。

Subproblems

$c(i, j) = editdistance(x[i:], y[j:]), 0 \leq i \lt |x|, 0 \leq j \lt |y|$

一共有 $\theta(|x| \cdot |y|)$ 个 subproblems

Guessing

• delete x[i]

• insert y[j]

• replace x[i] by y[i]

Recurrence

当 $i < |x|$ 且 $j < |y|$ 时：

$$C(i, j) = max \{delete \space x[i] + c(i+1, j), insert \space y[j] + c(i, j+1), replace \space x[i] + c(i+1, j+1)\}$$

基本 case：

$C(|x|, |y|) = 0$

Topological order

如图所示：

edit distance - topological order

从下往上或者从右往左皆可，总体时间复杂度为 $\theta(|x| \cdot |y|)$

Original problem

$C(0, 0)$

Knapsack（背包问题）

有一个大小为 S 的背包，你有 n 个 items 想要放进背包中，每个物品都有大小 $s_i$ 和价值 $v_i$，目标是找到一种最优放法，使得背包中装下价值最多的物品。

Subproblems

找到一种最优放法将剩余的物品 $items[i:]$ 放入剩余空间为 X 的背包中，subproblems 的数量为 $O(nS)$

Guessing

是否放入第 i 个物品

Recurrence

$DP[i, X] = max(DP[i+1, X], v_i + DP[i+1, X-s_i] \ if \ s_i \leq X)$

base case:

$DP[n, X] = 0$

time/subproblem = $O(1)$

Topological order

for i in reversed(range(n)):
    for X in range(S):
        pass

整体时间复杂度为 $O(nS)$

Original Problem

$DP[0, S]$

Time Complexity

背包问题的时间复杂度并不能简单地描述成 polynomial time。它的输入为 n 个最大为 S 的数，因此输入的大小为 $O(nlgS)$ ，而算法的时间复杂度为 $O(nS)$ ，其中 $S$ 与 $lgS$ 之间是指数关系，因此该算法的计算复杂度实际上介于 exponential 和 polynomial 之间，通常称为 pseudo-polynomial。

参考

• MIT 6.006 Fall, Lecture 19, 20, 21 slides, video