动态规划（DP）基本思想
- 保存子问题的结果，避免重复计算
- 用额外的数据结构保存（备忘）
- 空间换时间
- 大问题可以由子问题推出（状态转移）
动态规划解题思路
$\color{blue}{\text{空间换时间，这是门艺术}}$
分解子问题
- 根据题目特点，合理划分解决问题的阶段，每个阶段都解决一个和原问题相同的子问题
- 子问题能解决，原问题就能解决
- 子问题的结果会被保存，确保每个子问题只计算一次
确定状态
- 对于每个子问题，相关变量的一组取值，叫做一个状态
- 一个状态的值，就是这个状态下，子问题的解
- 状态的集合，叫做本问题的状态空间
- 比如一个状态可以用 $k$ 个整数表示，状态空间一般是 $k$ 维数组
- 状态的值不一定是一个整数，可能是一个数据结构
状态转移
- 首先确定初始状态的值
- 确定状态之间如何迁移，即如何根据一个状态的值，计算出另一个状态的值
- 一般存在一个递推公式，叫做状态转移方程
动归能解决的问题的特点
- 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们称该问题具有最优子结构
- 无后效性：当前的若干个状态值一旦确定，则后续过程的演变就只与当前状态的值有关，和之前演变路径无关。以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，$\color{red}{\text{每个状态都是过去历史的一个完整总结}}$。
线性动态规划
线性DP，双序列DP
最长上升子序列问题（LIS）
分析：
$dp[i]= $”以数组$\color{orange}{\text{第 $i$ 个数结尾}}$的 $\color{orange}{\text{最长上升子序列}}$的最大长度”
$dp[i] = \max\{dp[j]\} + 1$，对于所有 $\color{orange}{j < i}$ 且满足 $a[j] < a[i]$
边界条件：$dp[1] = 1$
最终答案是 $\max\{dp[i]\}$，即求完 $dp$ 数组后再取 $\max$
时间复杂度 $O(n^2)$
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i]) // 上升子序列
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
二分优化版 $O(n\log n)$
int len = 1;
f[1] = a[1];
for (int i = 2; i <= n; ++i) {
if (f[len] < a[i]) f[++len] = a[i];
else {
int pos = std::lower_bound(f + 1, f + len + 1, a[i]) - f;
f[pos] = a[i];
}
}
最长上升子序列（LCS）
分析：
输入两个串 $s1, s2$，设 $f(i, j)$ 表示：$s_1$ 的左边 $i$ 个字符形成子串，与 $s2$ 左边的 $j$ 个字符形成的子串的最长公共子序列的长度($i, j$ 从 $1$ 开始算)
假定 $len1 = strlen(s1), len2 = strlen(s2)$
那么题目就是要求 $f(len1, len2)$
初始条件：
$f(i, 0) = 0, \ i = 1 \cdots len1$
$f(0, j) = 0, \ j = 1 \cdots len2$
$ f(i, j) = \begin{cases} f(i - 1, j - 1) + 1, & s1[i] = s2[j] \\\ max(f(i, j - 1), f(i - 1, j)), & s1[i] \neq s2[j] \end{cases} $
#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::string;
using std::max;
const int N = 1010;
int dp[N][N];
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
int n = s1.size(), m = s2.size();
s1 = ' ' + s1, s2 = ' ' + s2;
for (int i = 1; i <= n; ++i) dp[i][0] = 0;
for (int j = 1; j <= m; ++j) dp[0][j] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i] == s2[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[n][m] << '\n';
}
return 0;
}
背包动态规划
01背包
有 $N$ 个物品。第 $i$ 个物品的价值为 $v[i]$，重量为 $w[i]$。选一些物品装到容量为 $C$ 的背包，使得背包内物品在总重量不超过 $C$ 的前提下价值尽量大。
例题：采药
分析：
$f[i][j]$ 表示，取前 $i$ 种物品，背包容量为 $j$，能取到的最大价值。第 $i$ 个物品，我们有两种选择，拿或不拿。
$f[i][j] = \max(f[i - 1][j], f[i - 1][j - w[i]] + v[i])$
第二种情况限于 $j > w[i]$ 的情况
边界条件：$f[0][j] = f[i][0] = 0$
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= t; ++j) {
if (j >= w[i]) {
dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
滚动数组优化
for (int i = 1; i <= m; i++) {
for (int j = t; j >= c[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
