重点知识笔记

AcWing 算法基础课

动态规划

背包 dp

01 背包

每个物品最多用一次

DP：

状态表示 f(i, j)：决定需要几个维度表示一个状态
- 状态集合：所有状态构成的集合
  - 所有选法的集合
  - 条件
    1. 只从前 i 个物品里选
    2. 总体积 <= j
- 状态属性：最大值、最小值、数量
状态计算 f(N, V)：集合划分
- 不包含第 i 个物品：f(i-1, j)
- 包含第 i 个物品：f(i-1, j-v[i]) + w[i]
- => f(i, j) = max( f(i-1,j), f(i-1,j-v[i])+w[i] )

DP 优化：对状态做等价变形

状态：未知数

完全背包

每个物品可以用无限次

状态计算：
- 不包含第 i 个物品：f(i-1, j)
- 包含第 i 个物品 k 个：f(i-1, j-k*v[i]) + k*w[i]
- => f(i, j) = max( f(i-1,j), f(i-1,j-v[i])+w[i] )

多重背包

每个物品最多用 Si 次

完全背包的方法不适用，需要用二进制优化：

将 Si 拆分成：1, 2, 4, 8, ..., 2^k, (Si-2^(k+1))，再用 01 背包的方式求解

分组背包

每组最多选 Si 个

线性 dp

最长上升子序列

状态表示 f[i]
- 集合：所有以第 i 个数结尾的上升子序列
- 属性：Max
状态计算：f[i] = max(f[j]+1), j=0,1,2,...,i-1

最长公共子序列

状态表示 f[i, j]
- 集合：所有在第一个序列的前 i 个字母中出现，且在第二个序列的前 j 个字母中出现的子序列
- 属性：Max
状态计算 f[i, j]
- 不包含 i, j：f[i-1, j-1]
- 包含 i，不包含 j：f[i-1, j]
- 包含 j，不包含 i：f[i, j-1]
- 包含 i， j：f[i-1, j-1] + 1

区间 dp

石子合并

状态表示 f[i, j]
- 集合：所有将第 i 堆石子到第 j 堆石子合并为一堆石子的合并方法
- 属性：Min
状态计算 f[i, j]
- 区间长度：1, 2, 3, ..., k-1，k=j-i+1

计数 dp

整数划分

数位 dp

计数问题

状压 dp

蒙德里安的梦想

最短 Hamilton 路径

状态表示 f[i, j]
- 集合：所有从 0 走到 j，走过的所有点是 i 的所有路径
- 属性：Min
状态计算根据倒数第二个点是哪个点分类
- 倒数第二个点：0, 1, 2, ..., n-1
- f(i-{j}, k) + a(k, j)

树形 dp

没有上司的舞会

状态表示
- 集合
  - f[u, 0]：所有从以 u 为根的子树中选择，并且不选 u 这个点的方案
  - f[u, 1]：所有从以 u 为根的子树中选择，并且选择 u 这个点的方案
- 属性：Max
状态计算：递归
- f(u, 0)：递归计算子节点 f(s1, 0), f(s1, 1), f(s2, 0), f(s2, 1)
- f(u, 0) + max(f(s1, 0), f(s1, 1)) + max(f(s2, 0), f(s2, 1))
- f(u, 1) + f(s1, 0) + f(s2, 0)

记忆化搜索

滑雪

注意：必须是拓扑图，不能有环

状态表示 f[i, j]
- 集合：所有从 (i, j) 开始滑的路径
- 属性：Max
状态计算：分类讨论，向上、向下、向左、向右
- 向右：f(i, j+1) + 1
- 其他方向同理