Dynamic Programming

动态规划

什么是 DP?

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

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

  • 常常可以用于优化问题(min/max),如最短路径

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

  • careful brute force

  • recursion + "re-use"

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

  • Fibonacci numbers

  • Shortest Paths

Fibonacci Numbers

斐波那契数列定义如下:

F1=F2=1;Fn=Fn1+Fn2F_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(2n2)O(2^{\frac{n}{2}})

T(n)=T(n1)+T(n2)+O(1)2T(n2)+O(1)O(2n2)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(1) ,因此整体复杂度为 O(n)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 之间的最短路径 δ(s,v)\delta(s, v) ,即 single-pair-shortest-path problem (SSSP)

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

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

δ(s,v)=mini(δ(ui,v)+w(ui,v))\delta(s, v) = \min_{i}{(\delta(u_i, v) + w(u_i, v))}

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

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

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

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

如果图中存在环,怎么办?

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

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

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

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

time=θ(VvVindegree(V))=θ(VE)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

FkF_k for 1kn1 \leq k \leq n

δk(s,v)\delta_{k}(s, v) for vVv \in V , 0k<V0 \leq k \lt |V| = min s-> v path using \leq k edges

2

no need to guess

edge into v (if any)

3

Fk=Fk1+Fk2F_k = F_{k-1} + F_{k-2}

δk(s,v)=min{δk1(s,u)+w(u,v)(u,v)E}\delta_{k}(s, v) = min \{ \delta_{k-1}(s, u) + w(u, v) | (u, v) \in E \}

4

for k=1,...,nk = 1, ..., n

for k=0,1,...,V1k = 0, 1, ..., |V|-1

for vVv \in V

5

FnF_n

δV1(s,v)\delta_{|V|-1}(s, v) for a=ba = 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)=badness(i, j) = \infty

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

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

Define Subproblems

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

Guessing

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

Recurrence

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

Order

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

Solution

DP[0]

Parent Pointers

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

序列问题中 subproblems 的结构

  • suffixes: x[i:]x[i:]

    • text justification

    • knapsack (more than just suffixes)

  • prefixes: x[:i]x[:i]

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

    • edit distance

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

  • Parenthesization

  • Edit Distance

  • Knapsack

Parenthesization

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

parenthesization

Subproblems/Guessing

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

A[0]A[1]...A[n1]=(A[0]A[1]...A[k1])(A[k]A[k+1]...A[n1])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]X[i:j]

Recurrence

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

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

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

Topological order

以 subsequence 的距离,从小到大

Original Problem

DP[0,n]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:]),0i<x,0j<yc(i, j) = editdistance(x[i:], y[j:]), 0 \leq i \lt |x|, 0 \leq j \lt |y|

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

Guessing

  • delete x[i]

  • insert y[j]

  • replace x[i] by y[i]

Recurrence

i<xi < |x|j<yj < |y| 时:

C(i,j)=max{delete x[i]+c(i+1,j),insert y[j]+c(i,j+1),replace x[i]+c(i+1,j+1)}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)=0C(|x|, |y|) = 0

Topological order

如图所示:

edit distance - topological order

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

Original problem

C(0,0)C(0, 0)

Knapsack(背包问题)

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

Subproblems

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

Guessing

是否放入第 i 个物品

Recurrence

DP[i,X]=max(DP[i+1,X],vi+DP[i+1,Xsi] if siX)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]=0DP[n, X] = 0

time/subproblem = O(1)O(1)

Topological order

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

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

Original Problem

DP[0,S]DP[0, S]

Time Complexity

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

参考

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