动态规划——从入门到入门

2019-08-10

2022-03-19

阅读次数: 1000000

[src: xkcd]

前言

动态规划一直是我很困扰的一个问题，最近读了一些资料，写了一些代码，顺便把一些经典问题的思路捋了捋，并把过程记录下来。注意：本文内容非常多！

序列相关问题

这类问题通常写作最XX子序列的问题，实际上是是一类 最优子结构 问题，往往能用动态规划轻松解决。

最长上升子序列（LIS）

在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。注意最长递增子序列中的元素在原序列中不一定是连续的。

解法

值得一提的是 —— 这类问题一般只要求出最优解就可以。

设序列 \(s\) 的第 \(i\) 个元素为 \(s_i\)，以第 \(i\) 个元素结束的 LIS 为 \(\text{LIS}(i)\)，\(\text{LIS}(i)\) 长度为 \(D_{i}\)，那么 \(D_{i}\) 只可能等于 \(D_j+1\)（\(0 \le j \lt i\)），即 \(\text{LIS}(i)\) 一定是某个 \(\text{LIS}(j)\) 的尾部增添 \(s_i\) 构成的，约束 \(s_j \lt s_i\) 并取所有 \(\text{LIS}(j)\) 的最大值赋给 \(D_{i}\)。边界 \(D_0=0\)，从 \(D_0\) 转移意味着 \(s_i\) 不满足任何 \(s_j \lt s_i\) ，则 \(\text{LIS}(j)\) 是仅含有 \(s_i\) 的单元素序列。总的结果是 \(\displaystyle \max_{0 \lt i \le n} (D_i)\)。数学表达如下：

\[D_{i}= \displaystyle \max_{0 \le j \lt i, s_j \lt s_i} (D_j)+1\]

这类表达式被称作 状态转移方程。

#define n 9
int s[n] = {10, 11, 13, 9, 6, 5, 4, 7, 14};
int D[n] = {};
for (int i = 0; i < n; ++i)
    D[i] = 1;
for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (s[j] < s[i])
            D[i] = max(D[i], D[j] + 1);
return *max_element(D, D + n);

优化

上面解的时间复杂度是 \(O(n^2)\)，使用二分法的时间复杂度是 \(O(n\log(n))\)，动态规划方法除了实现更容易似乎没有什么优势。实际上，换个思路，动态规划方法也能将时间复杂度降低到 \(O(n\log(n))\)。

设序列 \(s\) 的 长度为 \(k\) 的最优上升子序列 为 \(S^k\)（什么是最优暂不讨论），\(\{S^1,S^2,S^3...,S^n\}\)的尾元素值构成数组 \(D\)，\(D\) 初始化为空数组，空数组 \(D\) 可以看成是严格单调增的。考察每个元素 \(i\)，如果 \(D\) 里面所有 \(D_k\) 都满足 \(D_k \lt s_i\)，那么 \(D\) 数组尾部增添一个元素 \(s_i\)，LIS 长度增长 \(1\)；如果并非所有 \(D_k\) 都满足，那第一个恰不满足 \(D_k \lt s_i\) 的 \(D_k\) 应该被更新为 \(s_i\)，意味着该 \(D_k\) 对应的 \(S^k\) 被更新为 \(S^{k-1}\) 加上后缀 \(s_i\)，这个序列被认为是比原序列更优的，因为该序列性质和原序列相同，并持有持有更小的尾元素，更小的尾巴更有利于序列增长（若原序列加上后缀 \(s_i\) 为上升序列，则新序列加上后缀 \(s_i\) 必定也是上升序列，反之不成立。）

思路非常绕但是实现很简单：

int D[n] = {};
int len = 0;
for (int i = 0; i < n; ++i) {
    int pos = lower_bound(D, D + len, s[i]) - D;
    // lower_bound返回有序数组D中第一个不小于s[i]的元素对应的迭代器
    D[pos] = s[i];
    len = max(len, pos + 1);
}
return len;

lower_bound 实现了二分查找，故总的时间复杂度是 \(O(nlog(n))\)，这个算法比朴素的二分查找简洁，运行效率也更高。

求解最优方案

前面说过这类问题一般只要求出最优解就可以，但是如果需要求最优解具体对应的方案，依然可以解决。还要注意除非题目有约束，否则最优的方案可能不止一个。回顾下前面的解，也许立即就能意识到：状态转移的过程就是取方案的过程，只要记录下状态转移的过程，最优解的方案就到手了。

为了代码好写，这里假设最优方案唯一：

#define n 9
int s[n] = {0, 4, 9, 8, 7, 6, 5, 1, 2};
int D[n] = {};
int S[n] = {};
for (int i = 0; i < n; ++i)
    D[i] = 1;
for (int i = 0; i < n; ++i)
    S[i] = -1;
for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (s[j] < s[i] && D[i] < D[j] + 1) {
            D[i] = D[j] + 1;
            S[i] = j;
        }
int M = max_element(D, D + n) - D;
for (int i = M; i != -1; i = S[i])
    printf("%d->",S[i]);
print("^")

该算法回溯DP数组，以逆序输出解方案的序列。注意题设不能保证最优方案唯一时，本算法依然输出其中一个解（这个解特殊吗？）如果我们希望输出所有的解，那么需要用二维数组记录转移状态，而且回溯DP数组的算法也是 \(O(n^2)\) 的。后面的问题包括背包问题，都可以用此法给出解的方案，不再赘述。

最长公共子序列（LCS）

一个数值序列，如果分别是两个数值序列的子序列，且是所有符合此条件的序列中最长的，则称为已知序列的最长公共子序列。

解法

设两个序列分别为 \(X,Y\)，它们的 LCS 是 \(\text{LCS}(X,Y)\)，\(X^i\) 是序列 \(X\) 长度为 \(i\) 的前缀，\(Y^j\) 是序列 \(Y\) 长度为 \(j\) 的前缀，\(D_{i,j}\) 是 \(\text{LCS}(X^i,Y^j)\) 的长度。考察所有的前缀组合，当 \(X^i\) 和 \(Y^j\) 的尾元素相等（\(X^i_i=Y^j_j\)）时， \(X^i\) 和 \(Y^j\) 都是 \(\text{LCS}(X^i,Y^j)\) 的尾元素，或者说 \(\text{LCS}(X^{i-1},Y^{j-1})\) 尾部增添此元素构成 \(\text{LCS}(X^i,Y^j)\)，则 \(D_{i,j}=D_{i-1,j-1}+1\)；如果 \(X^i_i \ne Y^j_j\)，则 \(D_{i,j}\) 只能从 \(D_{i-1,j},D_{i,j-1},D_{i-1,j-1}\) 中的最大者转移，因为这些 \(D\) 分别对应的 \(\text{LCS}\) 一定也是 \(X^i\) 和 \(Y^j\) 的公共子序列，三个 \(D\) 分别对应：仅 \(X^i_i\) 更新 LCS，仅 \(Y^j_j\) 更新 LCS，\(X^i_i\) 和 \(Y^j_j\) 都不能更新 LCS。边界 \(D_{0,j}=0,D_{i,0}=0\)：

\[same(x,y)= \begin{cases} 0 &\text{if } s_i \ne t_j \\ 1 &\text{if } s_i = t_j \end{cases}\]

\[D_{i,j}=\max\{ D_{i-1,j-1}+same(X_i, Y_j), D_{i-1,j}, D_{i,j-1} \}\]

实现细节

因为 \(D_{i-1,j-1}\) 小于 \(D_{i-1,j-1}+same(X_i, Y_j)\)，所以它没有办法影响状态转移，可以从 \(\max\) 函数里去除，实际上，\(D_{i-1,j-1}\)一定最小的，\(D_{i-1,j-1}+1\) 一定是最大的。

char x[] = "abcde";
char y[] = "accabcdcced";
int n = strlen(x);
int m = strlen(y);
int D[2][m]; // VLA，在C++里属于GNU扩展功能，可以动态分配内存或用vector
memset(D, 0, 2 * m * 4);
for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        D[(i + 1) % 2][j + 1] = max(D[i % 2][j] + int(x[i] == y[j])),
                                    D[i % 2][j + 1],
                                    D[(i + 1) % 2][j]);
return D[n % 2][m];

因为二维数组中，元素依赖的项目只有上一行 \(i-1\)，上面的算法交替使用 \(2 \times m\) 数组的行来节省空间复杂度。这是一种通用的优化动态规划空间复杂度的方法。

扩展阅读

LCS 实际上是很多实际问题的基础，比如著名的GNU diff。正因为如此，许许多多的科学工作者研究了这个问题，并给出了一些一定条件下的更优解。读者可以自行阅读wiki。

编辑距离

编辑距离可以看成 LCS 问题的扩展，因为比较实用且变种较多所以额外提及一下：

在计算语言学和计算机科学中，编辑距离是一种通过计算将一个字符串转换为另一个字符串所需的最小操作数来量化两个字符串（例如单词）彼此之间有多么不同的方式。

Levenshtein距离允许删除，插入和置换。

最长公共子序列（LCS）距离仅允许插入和删除。

Hamming距离仅允许替换，因此，它仅适用于具有相同的长度的字符串。

Damerau-Levenshtein距离允许插入，缺失，置换，和交换的两个相邻的字符。

Jaro距离只允许交换的两个相邻的字符。

拼写校正，DNA序列相似度分析，图片相似度等问题都是编辑距离的实际应用。这里给出最复杂的求Damerau-Levenshtein距离的状态转移方程，假设所有操作的费用都是1，思路类似 LCS，边界 \(D_{0,0}=0\)：

\[D_{i,j}=\min \begin{cases} D_{i-1,j}+1 &\text{if } i \gt 0 \\ D_{i,j-1}+1 &\text{if } j \gt 0 \\ D_{i-1,j-1} + same(s_i, t_j) &\text{if } i \gt 0, j \gt 0 \\ D_{i-2,j-2} + 1 &\text{if } i \gt 1, j \gt 1, s_i=t_{j-1}, s_{i-1}=t_j \end{cases}\]

尽管状态转移方程的项很多，但是代码很好写，注意如果费用不是1，甚至费用不是定值，方程稍加修改就能使用，实际编码时，可以额外初始化 \(D_{0,j}=j, D_{i,0}=i\) 来减少内层循环中的条件判断。

背包问题

背包问题是一类解法可以优化到伪多项式时间复杂度的NP-C问题，这类问题也常常被作为动态规划方法的入门问题被提及，最著名的教程就是《背包问题九讲》

0-1背包问题

Q：有 n 件物品，每件物品有其对应的重量 \(w_i\) 和价值 \(v_i\)，有一个总重量限制为 \(W\) 背包，求背包能装下的最大总价值

解法

设\(D_{i,j}\)为前 \(i\) 种物品在重量限制 \(j\) 下所能取出的最大值（限重 \(j\) 的背包所能装下的最大价值）。对第 \(i\) 种物品都可以有取与不取两种选择，假设前 \(i-1\) 种物品在重量限制 \(j\) 下能获得的最大价值为 \(D_{i-1,j}\)，如果选第 \(i\) 种物品，\(D_{i,j}\) 应为 \(D_{i-1,j-w_i}+v_i\)；不选的话，\(D_{i,j}\) 为 \(D_{i-1,j}\)。二者中更大者为问题的解：

\[D_{i,j}= \max \{ D_{i-1,j-w_i}+v_i, D_{i-1,j} \}\]

实现细节

容易得知DP数组的边界 \(D_{0,0}=0\)，最终解为 \(D_{n,W}\)，当 \(j \lt w_i\) 时则意味着剩余重量已经不能支持取该物品了，可以直接置 \(D_{i,j}=D_{i-1,j}\)。该算法的时间复杂度与空间复杂度均为 \(O(nW)\)，相较之下，直接写成深搜时大量情况被重复计算，时间复杂度是 \(O(2^n)\)。

#define n 5
#define W 7

int w[n] = {2,4,3,4,3};
int v[n] = {1,5,3,4,2};

int D[n + 1][W + 1] = {{}};
for (int i = 0; i < n; ++i)
    for (int j = 0; j <= W; ++j)
        if (j < w[i])
            D[i + 1][j] = D[i][j];
        else
            D[i + 1][j] = max(D[i][j], D[i][j - w[i]] + v[i]);
return D[n][W];

注意 \(D\) 下标 1 指代第一种物品，\(w,v\) 下标 0 指代第一种物品。

《背包问题九讲》提到一个初始化细节，将 \(D_{0,j}(j \ne 0)\) 的值全置为 -inf 时，得出的解同时约束已选的物品总重恰好等于 \(W\)，因为此时所有“非完全填充”的中间状态都被移除了，合法解一定直接或间接地从 \(D_{0,0}\) 转移。

优化

\(D_{i,j}\) 由 \(D_{i-1,j-w_i}+v_i\) 与 \(D_{i-1,j}\) 两个子问题递推而来，我们颠倒内层循环的顺序（\(j\) 从大到小迭代），并用一维数组D[W+1]代替二维数组D[n+1][W+1]，计算到 \(i\) 时，就能使\(D_{j-w_i}\) 始终持有 \(D_{i-1,j-w_i}\) 的值，并把空间复杂度优化到 \(O(W)\)。此时还能改进循环下界，省去分支判断（\(j \lt w_i\) 时不修改数组即完成状态转移）

int D[W + 1] = {};
for (int i = 0; i < n; ++i)
    for (int j = W; j >= w[i]; --j)
        D[j] = max(D[j], D[j - w[i]] + v[i]);
return D[W];

《背包问题九讲》¹中还提到一个不太显然的优化，该问题中循环还有一个下界：\(W-\sum_{k=i+1}^n w_k\)，则共同下界为两者中的更大值，即代码中 j 的循环条件改为：

j >= max(w[i], W - accumulate(w + i + 1, w + n, 0))

我这样理解：已知结果为 D[W]，最后一次做外层循环时，D[W] 所需要先前的 D[W-w[n]]，而 D[W-w[n]] 又需要再先前的 D[W-w[n]-w[n-1]] …… 依此类推，则对于每一轮外层循环而言，其内层循环都可以给出下界 \(W-\sum_{k=i+1}^n w_k\)。对应这样一种情况，到选择某个物品时，剩余价值量对于全选剩下的物品也足够的话，\(j\) 小于该剩余价值量情况不会被最终结果用到。

可以预先好计算下界值以避免二重循环内重复计算下界，但是聪明的现代编译器往往可以自行处理该优化。

该改进所能减少的计算次数因数据而异，画个折线图分析一下，横轴代表 \(i\)，纵轴代表该 \(j\)，围成的矩形可以看作二维 DP 数组的每个元素。折线对应下界的值，蓝紫色区域对应引入另一个下界所省去的计算。

显然 W 相对越大，该下界越有效。对数据进行预处理也可以进一步优化下界，将原始数据按键值 \(w_i\) 以降序排序后，该下界更加有效。到这里，背包问题的解应该比较完美，但是时间复杂度依旧为 \(O(nW)\)

读者可以自行验证该结论，以空格分隔输入 \(w_i\) 的值，再输入 \(W\) 的值，刷新图表

w[i]: W:

换个角度

因为算法的时间复杂度为 \(O(nW)\)，当物品的 \(w\) 有较大的取值范围，\(W\) 也是较大值的话，这个解的时间复杂度无法令人满意。如果 \(W\) 和 \(w_i\) 有最大公约数的话，在做动态规划之前除掉这个数可以大幅提高性能，如果最大公约数不存在，或者除掉后 \(W\) 依然是很大的值，那我们不妨换个思路。

设 \(D_{i,j}\) 为前 \(i\) 种物品在总价值恰好为 \(j\) 的方案下能做到的最小体积，\(0 \lt j \le \sum{v_i}\)，转移方程：

\[D_{i,j}= min \{ D_{i-1,j-v_i}+w_i, D_{i-1,j} \}\]

原问题的最终解为 \(\displaystyle \max_{0 \lt j \le \,D_{n, j} \le W}(j)\)，该方法思路有点类似于 LIS 的优化方法。

int S = accumulate(v, v + n, 0);
int D[S + 1]; // VLA
memset(D, 0x3f, S * 4);
D[0] = 0;
for (int i = 0; i < n; ++i)
    for (int j = S; j >= v[i]; --j)
        D[j] = min(D[j], D[j - v[i]] + w[i]);
for (int i = S; i >= 0; --i)
    if (D[i] <= W) {
        cout << i << '\n';
        break;
    }

易知此算法时间复杂度为 \(O(n\sum{v_i})\)

完全背包问题

Q：有 n 种物品，每种有无穷多个，每种物品有其对应的重量 \(w_i\) 和价值 \(v_i\)，求在总重量限制为 \(W\) 下取出最高价值的方案

解法

类比前文的思考方法，对第 \(i\) 种物品有 \(k\) 种选择，其中最大值为当前约束下的最优决策，很容易写出以下递推公式和代码：

\[D_{i,j}= \displaystyle \max_{k=0}^{ \lfloor j/w[i] \rfloor} (D_{i-1,j-k \cdot w_i}+k \cdot v_{i})\]

int D[W + 1] = {{}};
for (int i = 0; i < n; ++i)
    for (int j = W; j >= w[i]; --j)
        for (int k = 1; k * w[i] <= j; ++k)
            D[j] = max(D[j], D[i][j - k * w[i]] + k * v[i]);
return D[W];

该算法的时间复杂度是 \(O(nW \widehat{\frac{W}{w_i}} )\)，不是很让人满意，但是类比该方法容易给出一些变种背包问题的解。²

优化

《背包问题九讲》中直接将 0-1背包问题的空间优化代码的内层循环次序再次颠倒，即为完全背包问题的解，这里同时给出对应的状态转移方程和代码：

\[D_{i,j}= \max \{D_{i,j-w_i}+v_i,D_{i-1,j} \}\]

int D[W + 1] = {};
for (int i = 0; i < n; ++i)
    for (int j = w[i]; j <= W; ++j)
        D[j] = max(D[j], D[j - w[i]] + v[i]);
return D[W];

这里的 DP 数组从小到大更新，除此之外和0-1背包完全相同，意味着\(D_{i,j}\) 从 \(D_{i,j-w_i}+v_i\) 转移。这个解非常出乎意料，但是冷静下来，考虑 \(D\) 的意义，新问题规定物品可以重复选取，在加选第 \(i\) 种物品时，应该从可能已选选取 \(i\) 的情况转移。通过简单的方程变形能证明这个转移方程是正确的：

\(D_{i,j}= \displaystyle \max_{k=0}^{ \lfloor j/w[i] \rfloor} (D_{i-1,j-k \cdot w_i}+k \cdot v_{i})\)

\(~~~~~~~=\max \{ \displaystyle \max_{k=1}^{ \lfloor j/w[i] \rfloor} (D_{i-1,j-k \cdot w_i}+k \cdot v_{i}),D_{i-1,j} \}\)

\(~~~~~~~let~~k=t+1\)

\(~~~~~~~=\max \{ \displaystyle \max_{t=0}^{ \lfloor j/w[i] \rfloor-1} (D_{i-1,j-(t+1) \cdot w_i}+(t+1) \cdot v_{i}),D_{i-1,j} \}\)

\(~~~~~~~=\max \{ \displaystyle \max_{t=0}^{ \lfloor (j-w_i)/w[i] \rfloor} (D_{i-1,j-w_i-t \cdot w_i}+t \cdot v_{i})+v_i,D_{i-1,j} \}\)

\(~~~~~~~\because D_{i,j-w_i}=\displaystyle \max_{t=0}^{ \lfloor (j-w_i)/w[i] \rfloor}(D_{i-1,j-w_i-t \cdot w_i}+t \cdot v_{i})\)

\(~~~~~~~= \max \{D_{i,j-w_i}+v_i,D_{i-1,j} \}\)

二维费用的背包问题

Q：有 n 件物品，每件物品有其对应的重量 \(w_i\)、体积 \(u_i\) 和价值 \(v_i\)，求在总重量限制为 \(W\) 且总体积限制为 \(U\) 下取出最高价值的方案

这个背包同时限制重量与体积，类比0-1背包问题的解，只需将状态转移方程加一维：

\[D_{i,j,k}= \max \{ D_{i-1,j-w_i,k-u_i}+v_i, D_{i-1,j,k} \}\]

回顾前面 LCS 一章，增加DP数组维度是处理更多约束的通用方法。

更一般的背包问题

《背包问题九讲》中提到了一个概念——“泛化物品”。有时候，物品的价值不是固定值，而可以看成是一个函数 \(f(w)\)，在一个费用 \(w\) 下该物品呈现出价值 \(f(w)\)，理解“泛化物品”的定义对解决问题可能有帮助。

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。

把主件和附件的组合看成一个物品组，物品组的价值是自变量 \(w\) 的函数，这里物品组就是前文所述的“泛化物品”。再把一个物品组看成是0-1背包问题中的一个物品，这样未解决的问题就转化为已解决的问题，类比分组背包问题，容易给出：

\[D_{i,j}= \displaystyle \max_{k \in K_i} (D_{i-1,j-k}+f_i(k))\]

\(K_i\) 为物品组 \(i\) 的价值函数的定义域，\(f_i(k)\) 为一般物品 \(i\) 恰好为 \(k\) 重下的最大价值。\(f_{i}(k)\) 本身也是在物品组内用0-1背包的动态规划方法求得的。下面的代码可以用于提交OJ：

int n, m;
vector<int> W, V;
struct pt {
    int x;
    int fx;
}; // f(x)函数
using f_t = vector<pt>; // 减少k迭代次数，优化时间复杂度

struct tree {
    int idx;
    vector<tree> child;
    void u(int g, int i) {
        if (idx == g)
            child.push_back(tree{i});
        else
            for (auto &c : child)
                c.u(g, i);
    }
    f_t solve() {
        if (child.empty())
            return f_t{pt{W[idx], V[idx]}};
        vector<int> D(1);
        if (idx == 0)
            D.resize(m + 1); // 最外层背包不要求恰好装满
        else
            D.resize(m + 1, 0xc0c0c0c0); // “内层背包”要求恰好装满
        D[W[idx]] = V[idx];
        for (int i = 0; i < child.size(); ++i) {
            auto f = child[i].solve();
            for (int j = m; j >= W[idx] + W[child[i].idx]; --j)
                for (pt k : f) {
                    if (k.x > j)
                        break;
                    D[j] = max(D[j], D[j - k.x] + k.fx);
                }
        }
        f_t F;
        for (int i = 0; i <= m; ++i)
            if (D[i] > 0)
                F.push_back(pt{i, D[i]});
        return F;
    }
};

int main() {
    scanf("%d %d", &m, &n);
    m /= 10;
    W.resize(n + 1), V.resize(n + 1); // [0]为w=0,v=0的空元素,也是所有的元素的祖先
    tree T{0};
    for (int i = 1; i <= n; ++i) {
        int w, a, g;
        scanf("%d %d %d", &w, &a, &g);
        w = w / 10;
        W[i] = w, V[i] = a * w;
        T.u(g, i);
    }
    f_t s = T.solve();
    printf("%d", s[s.size() - 1].fx * 10);
    return 0;
}

这里的解能适应更广泛的情况（更多附件数/多级附件），时空复杂度也已优化到最佳（大概）。类似的问题还有选课得学分，都是一类物件间有依赖关系的背包问题，解法都是树形DP。讨论这类花式DP问题远远超出了笔者的能力，在OI相关书籍上可以找到到更多这类复杂DP问题。

数论和组合数学相关

TODO

整数划分

TODO

小结

和分治法的异同

《算法导论》中将 动态规划 和 分治法 作了比较： 动态规划 一般用于解决最优化问题，这种方法和 分治法 类似，也将问题分解为子问题，合并子问题的解得到原问题的解。但是 动态规划 和 分治法 就不同在 分治法 分治出的子问题是独立的，子问题之间没有交集；而 动态规划 两个问题可能有公共子问题。在分治法里，如果分解出相同的子问题，则问题会被重复求解； 动态规划 里这个子问题仅求解一次。

动态规划原理

《算法导论》15.3节中给出了易于被动态规划解决的问题的要素：

如果一个问题的最优解包含其子问题的最优解，我们就称此问题有 最优子结构 性质。
如果问题的递归算法会反复求解相同的子问题，我们就称此问题有 重叠子问题 性质。

实际上，不满足 最优子结构 性质的问题，动态规划一定是无能无力的，必须小心判断问题是否有 最优子结构 性质。³

《算法导论》为发掘最优子结构性质的过程，总结出了通用模式：

证明问题的最优解的第一个组成部分是做出一个选择
假定已经知道哪种选择才会得到最优解，不关心这种选择具体是如何得到的
确定选择会产生的子问题，尽量简单地刻画子问题空间
利用“剪切-粘贴”技术和反证法证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。假定子问题的解不是其自身的最优解，那么可以从原问题的解中“剪切”掉这些非最优的解，将最优解“粘贴”进去，从而得到原问题一个更优的解，这与最初的解是原问题的最优解矛盾

可以比对前文中具体问题的解法体会这个通用模式。

泛用型自宅机器人

想到哪写到哪

Algorithm

动态规划——从入门到入门

前言

序列相关问题

最长上升子序列（LIS）

解法

优化

求解最优方案

最长公共子序列（LCS）

解法

实现细节

更多个序列的 LCS

扩展阅读

编辑距离

背包问题

0-1背包问题

解法

实现细节

优化

换个角度

完全背包问题

解法

优化

二维费用的背包问题

更一般的背包问题

数论和组合数学相关

整数划分

小结

和分治法的异同

动态规划原理