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 个斐波那契数字,会如何做?

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

fibonacci_brute_force.py
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n-1) + fib(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]

通过观察我们可以发现,其实在计算过程中,每次只用到了之前两个斐波那契数,因此我们可以将记忆空间进一步缩小到 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

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

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

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

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

总结一下,本节用 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

以前两个例子为例:

根据这 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

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

Original Problem

Time Complexity

参考

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

Last updated