什么是 DP?
DP 是一种算法设计思路,它有两个主要特点:
用低复杂度(polynomial)的方法解决看似高复杂度(看似 exponential)的问题
常常可以用于优化问题(min/max),如最短路径
通常 DP 的手段是递归(recursion)和记忆(memoization),通过将问题递归地拆分成子问题,找到相同子问题,复用结果来降低问题的复杂度,所以它又可以理解成:
接下来我们通过几个例子来领会 DP 精神:
Fibonacci Numbers
斐波那契数列定义如下:
F 1 = F 2 = 1 ; F n = F n − 1 + F n − 2 F_1 = F_2 = 1; F_n = F_{n-1} + F_{n-2} F 1 = F 2 = 1 ; F n = F n − 1 + F n − 2 如果我们要求第 n 个斐波那契数字,会如何做?
我们很容易想到一种暴力解法,而且代码写起来非常好看:
Copy def fib(n):
if n <= 2:
return 1
else:
return fib(n-1) + fib(n-2)
我们可以画一下该解法的递归树:
但从递归树上不难观察到,很多节点的计算是重复的,因此如果我们能够只对重复节点计算一次,问题的复杂度就降下来了,于是就有以下解法:
Copy 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]
通过观察我们可以发现,其实在计算过程中,每次只用到了之前两个斐波那契数,因此我们可以将记忆空间进一步缩小到 2:
fibonacci_dp_optimized.py
Copy 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
注:这里的常数 1 指的是考虑到有可能出现没有 indegree 的节点。
如果图中存在环,怎么办?
可以把图转化成多层,每层都含有图中的所有节点,每次只能访问下一层的节点,如下图所示:
这样就成功地将有环图转化成了 DAG,达到降维攻击的目的。原问题就转化为:
总结一下,本节用 DP 的思想分析 SSSP,得到了类似的答案,这也证明了 DP 作为算法设计思想的魅力。
DP 设计的 5 个步骤
relate subproblem solutions
recurse + memoize/build DP table bottom-up
check computation graph is acyclic, and think about topological order
以前两个例子为例:
Shortest Paths (with cycle)
根据这 5 个步骤,再看一个例子:
Text Justification
text justification 要解决的问题就是如何将一段文字放入一个固定宽度的文本框中,使得文字整体感觉更美观 。它的实际应用很常见,比如 Microsoft Office Word,LaTeX 等。在早期的版本中,Microsoft Office Word 使用的是贪心算法,在每一行放入尽可能多的文字,因此就经常会出现下图中的排版:
但通过将第一行的 blah 移到第二行,我们可以获得一个更美观的排版,如下图所示:
首先,为了表示美观 ,我们提出一个 badness 函数:
Define Subproblems
Guessing
Recurrence
Order
Solution
DP[0]
Parent Pointers
实际上 DP[0] 并不是我们需要的结果,而是具体的换行位置,为了从 DP[0] 中得到换行位置,我们需要在计算过程中利用 parent pointers 来记录求解的路径,这也是利用 DP 求解各种类型问题后获取求解路径的惯用做法。
序列问题中 subproblems 的结构
knapsack (more than just suffixes)
本节使用 DP 解决 3 个新问题:
Parenthesization
Subproblems/Guessing
这是一个典型的序列问题,因此要么从第一次矩阵相乘开始思考,要么从最后一次矩阵相乘开始思考,显然,这里从最后一次矩阵相乘开始思考更符合逻辑。最后一次矩阵乘法一定是将整个序列分成两部分,如果两部分各自的最优计算顺序,也就不难算出最后一次矩阵乘法的最优计算顺序:
Recurrence
Topological order
以 subsequence 的距离,从小到大
Original Problem
Edit Distance
给定两个字符串 x & y,计算它们之间的最小编辑距离。这里的编辑包括 insert,delete 以及 replace,三者操作的成本不同。它的应用范围包括:
如果 insert 和 delete 的 cost 都为 1,replace 的 cost 为 ∞,那么最小 edit distance 就等价于 longest common subsequence。
Subproblems
Guessing
Recurrence
基本 case:
Topological order
如图所示:
Original problem
Knapsack(背包问题)
Subproblems
Guessing
是否放入第 i 个物品
Recurrence
base case:
Topological order
Copy for i in reversed(range(n)):
for X in range(S):
pass
Original Problem
Time Complexity
参考
通过一系列数学推导,可以得到这种解法的复杂度为 O ( 2 n 2 ) O(2^{\frac{n}{2}}) O ( 2 2 n ) :
T ( n ) = T ( n − 1 ) + T ( n − 2 ) + O ( 1 ) ≥ 2 T ( n − 2 ) + O ( 1 ) ≥ O ( 2 n 2 ) T(n) = T(n-1) + T(n-2) + O(1) \geq 2T(n-2) + O(1) \geq O(2^{\frac{n}{2}}) T ( n ) = T ( n − 1 ) + T ( n − 2 ) + O ( 1 ) ≥ 2 T ( n − 2 ) + O ( 1 ) ≥ O ( 2 2 n ) 以上解法充分体现了,通过 memoization 来复用重复计算的结果,降低计算复杂度的思想,每个子问题的复杂度为 O ( 1 ) O(1) O ( 1 ) ,因此整体复杂度为 O ( n ) O(n) O ( n ) 。
问题描述:找到图中,节点 s 与 v 之间的最短路径 δ ( s , v ) \delta(s, v) δ ( s , v ) ,即 single-pair-shortest-path problem (SSSP)
同样可以从暴力思路开始,假设 δ ( s , v ) \delta(s, v) δ ( s , v ) 如下图所示:
从最后一条边 ( u , v ) (u,v) ( u , v ) 开始,假设能够到达 v v v 的节点有多个, u 1 , u 2 , u 3 , . . . u n u_1, u_2, u_3, ... u_n u 1 , u 2 , u 3 , ... u n ,假设我们已经知道了 δ ( s , u i ) , i = 1 , 2 , . . . , n \delta(s, u_i), i = 1, 2, ..., n δ ( s , u i ) , i = 1 , 2 , ... , n ,那么可以得到:
δ ( s , v ) = min i ( δ ( u i , v ) + w ( u i , v ) ) \delta(s, v) = \min_{i}{(\delta(u_i, v) + w(u_i, v))} δ ( s , v ) = i min ( δ ( u i , v ) + w ( u i , v )) 接着依次去递归 δ ( u i , v ) \delta(u_i, v) δ ( u i , v ) ,在 base case δ ( s , s ) = 0 \delta(s, s) = 0 δ ( s , s ) = 0 作用下,得到结果。可以想象,暴力思路的递归树呈现指数增长,这并不是一个高效的方法。但需要注意的是,这里暂时只考虑有向无环图的情形,后续会介绍在存在环、存在负权重环的情形下如何解决 SSSP。
有了 Recursion,减少重复计算的方法就是 Memoization,只要记住计算过程中所有的 δ ( s , v ) , v ∈ V \delta(s, v), v \in V δ ( s , v ) , v ∈ V 即可。这种解法的复杂度为:
t i m e = ∑ v ∈ V i n d e g r e e ( v ) + 1 = O ( V + E ) time = \sum_{v \in V}{indegree(v) + 1} = O(V+E) t im e = v ∈ V ∑ in d e g ree ( v ) + 1 = O ( V + E ) δ k ( s , v ) = δ ( s , v ) w i t h ≤ k e d g e s \delta_{k}(s, v) = \delta(s, v) \ with \leq k \ edges δ k ( s , v ) = δ ( s , v ) w i t h ≤ k e d g es k 取多少,即 DAG 有多少层合适?答案就是 ∣ V ∣ |V| ∣ V ∣ ,理由与 Bellmand-Ford 如出一辙,且实际上这就是 Bellmand-Ford。分析它的递归树,可以知道,整个递归过程共有 ∣ V ∣ 2 |V|^2 ∣ V ∣ 2 个子问题,且每个子问题消耗的时间为 O ( V ) O(V) O ( V ) ,粗略计算复杂度为 O ( V 3 ) O(V^3) O ( V 3 ) ,但仔细思考,同暴力解分析中的 indegree 求和过程,更精确的算法复杂度为:
t i m e = θ ( V ∑ v ∈ V i n d e g r e e ( V ) ) = θ ( V E ) time = \theta(V \sum_{v \in V} indegree(V)) = \theta (VE) t im e = θ ( V v ∈ V ∑ in d e g ree ( V )) = θ ( V E ) for , =
min s-> v path using k edges
如果本行所有单词及其间空格总长度大于文本框宽度: b a d n e s s ( i , j ) = ∞ badness(i, j) = \infty ba d n ess ( i , j ) = ∞
如果本行所有单词及其间空格总长度小于文本框宽度: b a d n e s s ( i , j ) = ( w p a g e − w w o r d s ) 3 badness(i, j) = (w_{page} - w_{words})^3 ba d n ess ( i , j ) = ( w p a g e − w w or d s ) 3
那么 text justification 目的就是找到合适的排版方式使得 ∑ b a d n e s s \sum {badness} ∑ ba d n ess 最小。
为 words[i:] 找到最小的 ∑ b a d n e s s \sum {badness} ∑ ba d n ess 划分,subproblems 的数量为 θ ( n ) \theta(n) θ ( n ) ,这里的 n n n 表示单词的数量
以哪个单词作为本行的结尾,共有 O ( n ) O(n) O ( n ) 种可能
D P [ i ] = m i n j ( b a d n e s s ( i , j ) + D P [ j ] ) , j ∈ [ i + 1 , n + 1 ] DP[i] = min_{j}{(badness(i, j) + DP[j])}, j \in [i+1, n+1] D P [ i ] = mi n j ( ba d n ess ( i , j ) + D P [ j ]) , j ∈ [ i + 1 , n + 1 ] ,且 D P [ n ] = 0 DP[n] = 0 D P [ n ] = 0 ,每个子问题的时间复杂度为 θ ( n ) \theta(n) θ ( n )
根据计算图可以发现,从 DP[n] 倒着计算到 DP[0] 是符合拓扑排序的,因此也可以算出总体的时间复杂度为 θ ( n 2 ) \theta(n^2) θ ( n 2 )
suffixes: x [ i : ] x[i:] x [ i : ]
prefixes: x [ : i ] x[:i] x [ : i ]
sub-sequences: x [ i : j ] x[i:j] x [ i : j ]
在矩阵乘法中,虽然没有交换律,但有结合律,因此在计算 A [ 0 ] ⋅ A [ 1 ] ⋅ . . . ⋅ A [ n − 1 ] A[0] \cdot A[1] \cdot ... \cdot A[n-1] A [ 0 ] ⋅ A [ 1 ] ⋅ ... ⋅ A [ n − 1 ] 时,总是存在一种最优的计算顺序,这种计算顺序可以使用加括号来表示,因此这个问题被称为 parenthesization,如下图所示:
A [ 0 ] ⋅ A [ 1 ] ⋅ . . . ⋅ A [ n − 1 ] = ( A [ 0 ] ⋅ A [ 1 ] ⋅ . . . ⋅ A [ k − 1 ] ) ⋅ ( A [ k ] ⋅ A [ k + 1 ] ⋅ . . . ⋅ A [ n − 1 ] ) 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]) A [ 0 ] ⋅ A [ 1 ] ⋅ ... ⋅ A [ n − 1 ] = ( A [ 0 ] ⋅ A [ 1 ] ⋅ ... ⋅ A [ k − 1 ]) ⋅ ( A [ k ] ⋅ A [ k + 1 ] ⋅ ... ⋅ A [ n − 1 ]) 对号入座,发现本问题的 subproblems 结构是 sub-sequences 形式,即 X [ i : j ] X[i:j] X [ i : j ]
D P [ i , j ] = min k ( D P [ i , k ] + D P [ k , j ] + c o s t ) , k = i + 1 , . . . , j DP[i, j] = \min_{k}(DP[i, k] + DP[k, j] + cost), k = i+1, ..., j D P [ i , j ] = min k ( D P [ i , k ] + D P [ k , j ] + cos t ) , k = i + 1 , ... , j
D P [ i , i + 1 ] = 0 DP[i, i+1] = 0 D P [ i , i + 1 ] = 0
cost/subproblem = θ ( j − i ) \theta(j-i) θ ( j − i ) = O ( n ) O(n) O ( n )
D P [ 0 , n ] DP[0, n] D P [ 0 , n ] ,最后使用 parent pointers 来构建最优解路径
c ( i , j ) = e d i t d i s t a n c e ( x [ i : ] , y [ j : ] ) , 0 ≤ i < ∣ x ∣ , 0 ≤ j < ∣ y ∣ c(i, j) = editdistance(x[i:], y[j:]), 0 \leq i \lt |x|, 0 \leq j \lt |y| c ( i , j ) = e d i t d i s t an ce ( x [ i : ] , y [ j : ]) , 0 ≤ i < ∣ x ∣ , 0 ≤ j < ∣ y ∣
一共有 θ ( ∣ x ∣ ⋅ ∣ y ∣ ) \theta(|x| \cdot |y|) θ ( ∣ x ∣ ⋅ ∣ y ∣ ) 个 subproblems
当 i < ∣ x ∣ i < |x| i < ∣ x ∣ 且 j < ∣ y ∣ j < |y| j < ∣ y ∣ 时:
C ( i , j ) = m a x { d e l e t e x [ i ] + c ( i + 1 , j ) , i n s e r t y [ j ] + c ( i , j + 1 ) , r e p l a c e 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)\} C ( i , j ) = ma x { d e l e t e x [ i ] + c ( i + 1 , j ) , in ser t y [ j ] + c ( i , j + 1 ) , re pl a ce x [ i ] + c ( i + 1 , j + 1 )} C ( ∣ x ∣ , ∣ y ∣ ) = 0 C(|x|, |y|) = 0 C ( ∣ x ∣ , ∣ y ∣ ) = 0
从下往上或者从右往左皆可,总体时间复杂度为 θ ( ∣ x ∣ ⋅ ∣ y ∣ ) \theta(|x| \cdot |y|) θ ( ∣ x ∣ ⋅ ∣ y ∣ )
有一个大小为 S 的背包,你有 n 个 items 想要放进背包中,每个物品都有大小 s i s_i s i 和价值 v i v_i v i ,目标是找到一种最优放法,使得背包中装下价值最多的物品。
找到一种最优放法将剩余的物品 i t e m s [ i : ] items[i:] i t e m s [ i : ] 放入剩余空间为 X 的背包中,subproblems 的数量为 O ( n S ) O(nS) O ( n S )
D P [ i , X ] = m a x ( D P [ i + 1 , X ] , v i + D P [ i + 1 , X − s i ] i f s i ≤ X ) DP[i, X] = max(DP[i+1, X], v_i + DP[i+1, X-s_i] \ if \ s_i \leq X) D P [ i , X ] = ma x ( D P [ i + 1 , X ] , v i + D P [ i + 1 , X − s i ] i f s i ≤ X )
D P [ n , X ] = 0 DP[n, X] = 0 D P [ n , X ] = 0
time/subproblem = O ( 1 ) O(1) O ( 1 )
背包问题的时间复杂度并不能简单地描述成 polynomial time。它的输入为 n 个最大为 S 的数,因此输入的大小为 O ( n l g S ) O(nlgS) O ( n l g S ) ,而算法的时间复杂度为 O ( n S ) O(nS) O ( n S ) ,其中 S S S 与 l g S lgS l g S 之间是指数关系,因此该算法的计算复杂度实际上介于 exponential 和 polynomial 之间,通常称为 pseudo-polynomial。
MIT 6.006 Fall, Lecture 19, 20, 21 slides,
1 ≤ k ≤ n 1 \leq k \leq n 1 ≤ k ≤ n δ k ( s , v ) \delta_{k}(s, v) δ k ( s , v ) 0 ≤ k < ∣ V ∣ 0 \leq k \lt |V| 0 ≤ k < ∣ V ∣ F k = F k − 1 + F k − 2 F_k = F_{k-1} + F_{k-2} F k = F k − 1 + F k − 2 δ k ( s , v ) = m i n { δ k − 1 ( 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 \} δ k ( s , v ) = min { δ k − 1 ( s , u ) + w ( u , v ) ∣ ( u , v ) ∈ E } k = 1 , . . . , n k = 1, ..., n k = 1 , ... , n k = 0 , 1 , . . . , ∣ V ∣ − 1 k = 0, 1, ..., |V|-1 k = 0 , 1 , ... , ∣ V ∣ − 1 δ ∣ V ∣ − 1 ( s , v ) \delta_{|V|-1}(s, v) δ ∣ V ∣ − 1 ( s , v )
recursion tree of brute force approach to nth fibonacci number
Greedy Approach to Text Justification
Dynamic Programming Approach to Text Justification
edit distance - topological order