4DP.typ

= 动态规划

== 背包问题

*01背包*

$N$ 个物品重量 $w_i$ 价值 $v_i$ ,背包总容量 V，每个物品只能选或者不选。$f(i, j)$ 表示选前 $i$ 个物品，背包最大体积为 $j$ 的情况下储存的属性（如最大价值，最小价值，物品数量最多，以下讨论最大价值）

$ f(i,j)=max(f(i-1,j),f(i-1,j-w_i)+v_i) $

改为滚动数组，从后向前遍历：

$ f(j)=(f(j),f(j-w_i)+v_i) $

*完全背包*

每个物品可以选无限次个。$f(i, j)$ 表示选前 $i$ 个物品，背包最大体积为 $j$ 的情况下储存最大价值

$ f(i,j)=max_(k=0)^(k->+∞)(f(i-1,j-k w_i)+k v_i) $

优化至二维：

$ f(i,j)=max(f(i-1,j),f(i,j-w_i)+v_i) $

改为滚动数组，从前向后遍历：

$ f(j)=max(f(j),f(j-w_i)+v_i) $

*多重背包*

最多选 $m$ 个物品的完全背包。$f(i, j)$ 表示选前 $i$ 个物品，背包最大体积为 $j$ 的情况下储存最大价值

$ f(i,j)=max_(k=0)^(k → m) (f(i-1,j-k w_i)+k v_i) $

使用二进制分组优化可降低至 $O(n V log m)$

*分组背包*

有 $N$ 组物品，第 $i$ 组物品有 $n$ 个物品，每个物品有重量 $w_i^k$ 和价值 $v_i^k$ ，背包总容量 $V$

$ f(i,j)=max(f(i-1,j),max_(k=1)^(k→n) (f(i-1,j-w_i^k)+v_i^k)) $


== 序列问题

*最长上升子序列（LIS）*

子序列是数组中不连续的一段，维护一个数组 $d$，$d[i]$ 表示长度为 $i$ 的上升子序列的末尾元素的最小值

- 若一个元素 $a[i]$ 大于 $d["len"]$，则 $d[++"len"] = a[i]$
- 否则在 $d$ 中二分找到第一个大于等于 $a[i]$ 的位置 $"pos"$，更新 $d["pos"] = a[i]$

最后答案是 $"len"$，最长上升子序列即 $d$ 数组，代码实现如下

```cpp
vector<int> d;
for (int i = 1; i <= n; ++i) {
  if (d.empty() || a[i] > d.back())
    d.push_back(a[i]);
  else
    *lower_bound(d.begin(), d.end(), a[i]) = a[i];
}
```

*最长公共子序列（LCS）*

求两个字符串 $s$ 和 $t$ 的最长公共子序列长度，子序列是字符串中不连续的一段。$f[i][j]$ 表示 $s$ 的前 $i$ 个字符和 $t$ 的前 $j$ 个字符的最长公共子序列长度，初始状态 $f[i][0]=0$ 和 $f[0][j]=0$，状态转移如下，答案是 $f[n][m]$

$ f[i][j] = cases(
  f[i-1][j-1] + 1 & comma s[i] = t[j],
  max(f[i-1][j], f[i][j-1]) & comma s[i] != t[j]
) $


*最长公共上升子序列（LICS）*

求两个字符串 $s$ 和 $t$ 的最长上升公共子序列长度，子序列是字符串中不连续的一段。$f[i][j]$ 表示 $s$ 的前 $i$ 个字符和 $t$ 的前 $j$ 个字符的最长上升公共子序列长度，初始状态 $f[i][0]=0$ 和 $f[0][j]=0$，状态转移如下，答案是 $f[n][m]$

$ f[i][j] = cases(
  f[i-1][j-1] + 1 & comma s[i] = t[j] comma s[i] > s[i-1],
  max(f[i-1][j], f[i][j-1]) & comma s[i] != t[j]
) $