\delta\_{k}(s, v) for v \in V , 0 \leq k \lt | V | =
min s-> v path using \leq k edges
for k = 0, 1, ..., | V | -1
for v \in V
| | 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 使用的是贪心算法，在每一行放入尽可能多的文字，因此就经常会出现下图中的排版：  但通过将第一行的 blah 移到第二行，我们可以获得一个更美观的排版，如下图所示：  首先，为了表示**美观**，我们提出一个 badness 函数： * 如果本行所有单词及其间空格总长度大于文本框宽度： $$badness(i, j) = \infty$$ * 如果本行所有单词及其间空格总长度小于文本框宽度： $$badness(i, j) = (w\_{page} - w\_{words})^3$$ 那么 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)$$ #### Order 根据计算图可以发现，从 DP\[n] 倒着计算到 DP\[0] 是符合拓扑排序的，因此也可以算出总体的时间复杂度为 $$\theta(n^2)$$ #### Solution DP\[0] ### Parent Pointers 实际上 DP\[0] 并不是我们需要的结果，而是具体的换行位置，为了从 DP\[0] 中得到换行位置，我们需要在计算过程中利用 parent pointers 来记录求解的路径，这也是利用 DP 求解各种类型问题后获取求解路径的惯用做法。 ## 序列问题中 subproblems 的结构 * suffixes： $$x\[i:]$$ * 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，如下图所示：  #### 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]$$ #### Recurrence $$DP\[i, j] = \min\_{k}(DP\[i, k] + DP\[k, j] + cost), k = i+1, ..., j$$ $$DP\[i, i+1] = 0$$ cost/subproblem = $$\theta(j-i)$$ = $$O(n)$$ #### 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|$$ 一共有 $$\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$$ #### Topological order 如图所示：  从下往上或者从右往左皆可，总体时间复杂度为 $$\theta(|x| \cdot |y|)$$ #### Original problem $$C(0, 0)$$ ## Knapsack（背包问题） 有一个大小为 S 的背包，你有 n 个 items 想要放进背包中，每个物品都有大小 $$s\_i$$ 和价值 $$v\_i$$，目标是找到一种最优放法，使得背包中装下价值最多的物品。 #### Subproblems 找到一种最优放法将剩余的物品 $$items\[i:]$$ 放入剩余空间为 X 的背包中，subproblems 的数量为 $$O(nS)$$ #### Guessing 是否放入第 i 个物品 #### Recurrence $$DP\[i, X] = max(DP\[i+1, X], v\_i + DP\[i+1, X-s\_i] \ if \ s\_i \leq X)$$ base case: $$DP\[n, X] = 0$$ time/subproblem = $$O(1)$$ #### Topological order ```python for i in reversed(range(n)): for X in range(S): pass ``` 整体时间复杂度为 $$O(nS)$$ #### Original Problem $$DP\[0, S]$$ ### 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)