# 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](/files/-LYjdlMaJjbDnsy9zlcB)

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

![](/files/-LZDKEY1LGNdnlSBqQFN)

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

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

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

![](/files/-LZDSOlTklZnJWv-FvoL)

这样就成功地将有环图转化成了 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](/files/-LZTTtxY8ASK_FUSYpDx)

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

![Dynamic Programming Approach to Text Justification](/files/-LZTUE2kWmQe9XdvTi8T)

首先，为了表示**美观**，我们提出一个 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](/files/-LZTzUtFLmQj2igI4CD-)

#### 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](/files/-LZU7vFAuioJbiYgxGSx)

从下往上或者从右往左皆可，总体时间复杂度为 $$\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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/dynamic-programming.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.