DP：
-
线性dp
-
P1091 [NOIP2004 提高组] 合唱队形
比较简单的一道题。求出以 \(i\) 结尾的最长上升子序列和以 \(i\) 为头的最长下降子序列，相加 \(-1\) 即可。
-
P1052 [NOIP2005 提高组] 过河
如果不考虑 \(L\) 的范围，那么就是一道简单的线性 dp 。
但是 \(L\) 很大，石头数量很少，所以每相邻两个石头的空隙一定很大。
前置知识：P3951 [NOIP2017 提高组] 小凯的疑惑给定两个数 \(p\) 和 \(q\) ，他们最大不能凑出的数是 \((p-1)(q-1)-1\) 。所以中间空隙过多一定是可以被凑出来的，即可以压缩中间的空隙，然后线性 dp 即可。
-
P1006 [NOIP2008 提高组] 传纸条
求出 \(2\) 条从 \((1,1)\) 到 \((n,m)\) 的路径。重复只算一次，求最大路径和。
水题，不多赘述。记录 \(dp_{A,B,C,D}\) 表示第一条走到 \((A,B)\) , 第二条走到 \((C,D)\) 。由于 \(A+B = C+D\) ，可以记录他们的和，优化掉一维。
-
P1541 [NOIP2010 提高组] 乌龟棋
记录 \(dp_{A,B,C,D}\) 表示用了 \(A\) 个 \(1\) 号卡片， \(B\) 个 \(2\) 号卡片， \(C\) 个 \(3\) 号卡片， \(D\) 个 \(4\) 号卡片。
暴力转移即可 \(F_{A,B,C,D}=\max (F_{A-1,B,C,D},F_{A,B-1,C,D},F_{A,B,C-1,D},F_{A,B,C,D-1})+cost_{A+2B+3C+4D}\)
-
P2679 [NOIP2015 提高组] 子串
前缀和优化线性 dp。（推式子题）
首先考虑如何 DP，然后再考虑如何优化。
状态表示：\(f_{i, j, k}\)表示只用 \(S\) 的前 \(i\) 个字母，选取了 \(k\) 段，可以匹配 \(T\) 的前 \(j\) 个字母的方案数。
状态计算：将 \(f_{i,j,k}\)表示的所有方案分成两大类：
- 不用 \(S_i\)，则方案数是 \(f_{i-1,j,k}\)；
- 使用 \(S_i\)，则方案数是 $ \sum f_{i-t,j-t,k-1}$，满足 \(S_{i-t+1}=T_{i-t+1}\)，\(t\) 从大到小枚举。
时间复杂度是 $ \mathcal{O} (nm2k)$。
我们发先 \(f_{i,j,k}\) 的第二项和 \(f_{i-1,j-1,k}\) 很像，可以考虑维护一个 \(tmp_{i,j,k}\)
- \(S_i=T_j\) , \(tmp_{i,j,k}=tmp_{i-1,j-1,k}+f_{i-1,j-1,k-1}\) 。
- \(S_i \neq T_j\)，\(tmp_{i,j,k}=0\) 。
（把式子展开可以发现 \(tmp\) 的规律）。
然后空间会爆，写滚动数组或者 01背包 倒序枚举优化掉第一维即可。
-
P5664 [CSP-S2019] Emiya 家今天的饭
求解所有方案数
\(f_{i,j}\) 表示前 \(i\) 种烹饪方式，做了 \(j\) 道菜的方案数。
-
状态转移：
第 \(i\) 种烹饪方式不做 \(f_{i,j}+= f_{i - 1,j}\) -
第 \(i\) 种烹饪方法做 \(1\) 道主要食材是 \(k\) 的菜：\(f_{i,j} += f_{i-1,j-1} * a_{i, k}\)
所有方案数量 $ A = \sum_{j = 1}^{n}f[n][j]$ 。
求解不合法方案：
\(dp_{i,j}\) 表示前 \(i\) 中烹饪方法，越界食材数 $ - $ 其他食材数 为 \(j\) 的方案数。
状态转移：
-
第 \(i\) 种烹饪方法不选：\(dp_{i,j} += dp_{i-1,j}\)
-
选越界食材 \(c\)：\(dp_{i,j} += dp_{i-1,j-1} * a_{i, c}\)
-
选其他食材 \(dp_{i,j} += dp_{i-1,j+1} * (s_i - a_{i, c})\)
所有方案数量： $ B = \sum dp_{n,j} (j > 0)$ 。
\(A-B\) 即可。
时间复杂度 \(\mathcal{O}(n ^ 2m)\) 。
\(Tips\)：
做差有可能为负数，把所有状态加一个 \(+n\) 的偏移量即可。 -
-
总结：
对于线性 dp的问题，一般状态定义为 \(f_{前\ i\ 个,满足 \ ....\ 状态}\)，状态可能很多，所以可能有很多维。
状态转移：考虑这个集合是由谁构成的，进行分类。比如分成 选 \(a\) 和不选 \(a\) ......
优化：如果状态过多，考虑滚动数组或者背包优化，转移中有求和，求最值等考虑用前缀和，单调队列优化。
-
-
区间dp
-
背包
-
状压dp
-
树形dp
-
倍增优化dp
贪心：
搜索：
-
DFS
-
BFS
-
剪枝
数学：
-
数论：
-
组合数学
图论：
-
拓扑排序
-
树
-
LCA
-
最短路
-
二分图
数据结构：
-
堆
-
并查集
-
线段树
-
单调队列
基础算法：
-
枚举
-
模拟
-
字符串
-
排序
-
二分
-
位运算
-
构造
-
哈希
-
找规律