---
description: 动态规划
---

# 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 个斐波那契数字，会如何做？

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

{% code title="fibonacci_brute_force.py" %}
```python
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
```
{% endcode %}

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

![recursion tree of brute force approach to nth fibonacci number](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LYjaZxTeih4ZBtVxa8K%2F-LYjdlMaJjbDnsy9zlcB%2FScreen%20Shot%202019-02-15%20at%201.35.22%20PM.jpg?alt=media\&token=003bcb48-7454-47c2-9b85-5f5a06d005d9)

通过一系列数学推导，可以得到这种解法的复杂度为 $$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}})
$$

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

{% code title="fibonacci_dp.py" %}
```python
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]
```
{% endcode %}

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

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

{% code title="fibonacci_dp_optimized.py" %}
```python
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
```
{% endcode %}

总结一下：

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

## Shortest Paths

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

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZDJRjekmzd7hdhXN6Q%2F-LZDKEY1LGNdnlSBqQFN%2FScreen%20Shot%202019-02-21%20at%2012.33.54%20PM.jpg?alt=media\&token=f75fdf72-f30e-49aa-99ed-99983e35c297)

从最后一条边 $$(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 的节点。

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

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZDJRjekmzd7hdhXN6Q%2F-LZDSOlTklZnJWv-FvoL%2FScreen%20Shot%202019-02-21%20at%201.09.35%20PM.jpg?alt=media\&token=8dc8c387-b0cf-4e66-823c-61dd396308b4)

这样就成功地将有环图转化成了 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$$  | <p><span class="math">\delta_{k}(s, v)</span>  for <span class="math">v \in V</span> , <span class="math">0 \leq k \lt |V|</span>  = <br>min s-> v path using <span class="math">\leq</span> k edges</p> |
| 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$$            | <p>for <span class="math">k = 0, 1, ..., |V|-1</span> </p><p>    for <span class="math">v \in V</span> </p>                                                                                              |
| 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](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZTNNLLce4Rh7uncuSS%2F-LZTTtxY8ASK_FUSYpDx%2FScreen%20Shot%202019-02-24%20at%203.50.02%20PM.jpg?alt=media\&token=f97896fa-0334-40fc-961e-a3ffead16069)

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

![Dynamic Programming Approach to Text Justification](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZTNNLLce4Rh7uncuSS%2F-LZTUE2kWmQe9XdvTi8T%2FScreen%20Shot%202019-02-24%20at%203.51.30%20PM.jpg?alt=media\&token=5879a953-9ac2-477b-89c5-f1a155c89658)

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

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

那么 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)$$&#x20;

#### Order

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

#### Solution

DP\[0]

### Parent Pointers

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

## 序列问题中 subproblems 的结构

* suffixes： $$x[i:]$$&#x20;
  * 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](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZTrqX3pNTyzFXWiK0n%2F-LZTzUtFLmQj2igI4CD-%2FScreen%20Shot%202019-02-24%20at%206.12.28%20PM.jpg?alt=media\&token=5303ef10-b824-45e5-b541-b246500882d3)

#### 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]$$&#x20;

#### Recurrence

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

$$DP[i, i+1] = 0$$&#x20;

cost/subproblem = $$\theta(j-i)$$ = $$O(n)$$&#x20;

#### 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|$$&#x20;

一共有 $$\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$$&#x20;

#### Topological order

如图所示：

![edit distance - topological order](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZTrqX3pNTyzFXWiK0n%2F-LZU7vFAuioJbiYgxGSx%2FScreen%20Shot%202019-02-24%20at%206.53.32%20PM.jpg?alt=media\&token=38498de0-ddba-4d3b-9ac0-1ce405a8c633)

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

#### Original problem

$$C(0, 0)$$&#x20;

## Knapsack（背包问题）

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

#### Subproblems

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

#### Guessing

是否放入第 i 个物品

#### Recurrence

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

base case:

$$DP[n, X] = 0$$&#x20;

time/subproblem = $$O(1)$$&#x20;

#### Topological order

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

整体时间复杂度为 $$O(nS)$$&#x20;

#### Original Problem

$$DP[0, S]$$&#x20;

### 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](https://www.youtube.com/watch?v=OQ5jsbhAv_M)
