Dynamic Programming
动态规划
什么是 DP?
DP 是一种算法设计思路,它有两个主要特点:
用低复杂度(polynomial)的方法解决看似高复杂度(看似 exponential)的问题
常常可以用于优化问题(min/max),如最短路径
通常 DP 的手段是递归(recursion)和记忆(memoization),通过将问题递归地拆分成子问题,找到相同子问题,复用结果来降低问题的复杂度,所以它又可以理解成:
careful brute force
recursion + "re-use"
接下来我们通过几个例子来领会 DP 精神:
Fibonacci numbers
Shortest Paths
Fibonacci Numbers
斐波那契数列定义如下:
如果我们要求第 n 个斐波那契数字,会如何做?
我们很容易想到一种暴力解法,而且代码写起来非常好看:
我们可以画一下该解法的递归树:
但从递归树上不难观察到,很多节点的计算是重复的,因此如果我们能够只对重复节点计算一次,问题的复杂度就降下来了,于是就有以下解法:
通过观察我们可以发现,其实在计算过程中,每次只用到了之前两个斐波那契数,因此我们可以将记忆空间进一步缩小到 2:
总结一下:
在 Fibonacci numbers 的例子中,我们通过观察递归树,找到重复计算节点,并进一步将计算过程转化为 DAG,理清不同子问题之间的依赖关系,按照依赖关系依次从小到大地解决子问题,同时通过 memoization 避免重复计算,从而最终解决原问题。
Shortest Paths
注:这里的常数 1 指的是考虑到有可能出现没有 indegree 的节点。
如果图中存在环,怎么办?
可以把图转化成多层,每层都含有图中的所有节点,每次只能访问下一层的节点,如下图所示:
这样就成功地将有环图转化成了 DAG,达到降维攻击的目的。原问题就转化为:
总结一下,本节用 DP 的思想分析 SSSP,得到了类似的答案,这也证明了 DP 作为算法设计思想的魅力。
DP 设计的 5 个步骤
define subproblems
guess (part of solution)
relate subproblem solutions
recurse + memoize/build DP table bottom-up check computation graph is acyclic, and think about topological order
solve original problem
以前两个例子为例:
根据这 5 个步骤,再看一个例子:
Text Justification
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 的结构
text justification
knapsack (more than just suffixes)
edit distance
本节使用 DP 解决 3 个新问题:
Parenthesization
Edit Distance
Knapsack
Parenthesization
Subproblems/Guessing
这是一个典型的序列问题,因此要么从第一次矩阵相乘开始思考,要么从最后一次矩阵相乘开始思考,显然,这里从最后一次矩阵相乘开始思考更符合逻辑。最后一次矩阵乘法一定是将整个序列分成两部分,如果两部分各自的最优计算顺序,也就不难算出最后一次矩阵乘法的最优计算顺序:
Recurrence
Topological order
以 subsequence 的距离,从小到大
Original Problem
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
Guessing
delete x[i]
insert y[j]
replace x[i] by y[i]
Recurrence
基本 case:
Topological order
如图所示:
Original problem
Knapsack(背包问题)
Subproblems
Guessing
是否放入第 i 个物品
Recurrence
base case:
Topological order
Original Problem
Time Complexity
参考
MIT 6.006 Fall, Lecture 19, 20, 21 slides, video
Last updated