线性 DP
线性 DP 一般是状态只有一维的 DP。
DP 一般是用于解决这样的一些问题：每一个子任务都具有相同的结构，同时我们只关心当前的状态是什么，不关系如何转移到这个状态的。
最长上升子序列
给定一个长度为 \(n\) 的序列 \(a\)，求这个序列的最长上升子序列。
设 \(f_i\) 表示以 \(i\) 结尾的最长上升子序列长度，对于每一个 \(i\)，枚举它的上一个元素是什么，\(f_i=(\max\limits_{a_j<a_i}) f_j + 1\).
洛谷 3842 / TBOJ1894 线段
显然我们只会走到每一行的线段左右端点位置，然后就停下来进入下一行。设 \(f_{i,0/1}\) 表示走完第 \(i\) 行，当前在左/右端点的最小答案。
转移只需要考虑从 \(i-1\) 到 \(i\) 要走多少步就好。
const int MAXN = 2e4 + 5;
int n, l[MAXN], r[MAXN], f[MAXN][2];void work() {cin >> n;for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i];l[0] = r[0] = 1;for (int i = 1; i <= n; ++i) {f[i][0] = min(f[i - 1][0] + (i != 1) + abs(r[i] - l[i - 1]) + r[i] - l[i],f[i - 1][1] + (i != 1) + abs(r[i] - r[i - 1]) + r[i] - l[i]);f[i][1] = min(f[i - 1][0] + (i != 1) + abs(l[i] - l[i - 1]) + r[i] - l[i],f[i - 1][1] + (i != 1) + abs(l[i] - r[i - 1]) + r[i] - l[i]);}int ans = min(f[n][0] + n - l[n], f[n][1] + n - r[n]);cout << ans << endl;
}
洛谷 1541 / TBOJ1410 乌龟棋
设 \(f_{i,j,k,h}\) 表示当前用了 \(i/j/k/h\) 张 1/2/3/4 牌，能拿到的最多价值，当前位置显然为 \(i+2j+3k+4h\)，转移枚举一下用了哪张牌到达的当前位置，即：\(f_{i,j,k,h}=\min f_{i',j',k',h} + a_{i+2j+3k+4h}\)。
背包 DP
这个东西板子考的不多，大概意思是有 \(n\) 个物品，背包容量为 \(m\)，每个物品有一个价值 \(v_i\) 和重量 \(w_i\)，要求在选出的物品重量之和不超容量的情况下最大化价值。
设 \(f_{i,j}\) 表示考虑前 \(i\) 个物品，当前最大容量为 \(j\) 的最大价值，每次转移枚举一下选不选 \(i\) 这个物品即可。
洛谷 1048 / TBOJ2350 采药
01 背包板子。
洛谷 1616 / TBOJ3454 疯狂的采药
完全背包板子。
洛谷 6771 / TBOJ4724 太空电梯
设 \(f_{i,j}\) 表示考虑前 \(i\) 个方块，能不能达到高度 \(j\)，每次转移就枚举当前方块选几个。
可能需要把第一维给滚动掉。
abc267d / TBOJ4725 Index × A(Not Continuous ver.)
设 \(f_{i,j}\) 表示当前考虑前 \(i\) 个元素，选了 \(j\) 个，转移就枚举当前这个元素选/不选。
#define int long long
const int MAXN = 2e3 + 5;
int n, m, a[MAXN], f[MAXN][MAXN];void work() {cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 0; i <= n; ++i) {for (int j = 1; j <= m; ++j) f[i][j] = LLONG_MIN / 2;}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] + a[i] * j);}}cout << f[n][m] << endl;
}
abc245c / TBOJ4726 Choose Elements
设 \(f_{i,0/1}\) 表示考虑前 \(i\) 个元素，第 \(i\) 个位置上选了 \(a/b\)，是否有一个合法序列。转移枚举当前位置选 \(a\) 还是选 \(b\) 即可。
const int MAXN = 2e5 + 5;
int n, k, a[MAXN], b[MAXN];
bool f[MAXN][2];void work() {cin >> n >> k;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];f[1][0] = f[1][1] = true;for (int i = 2; i <= n; ++i) {if (abs(a[i] - a[i - 1]) <= k) f[i][0] |= f[i - 1][0];if (abs(a[i] - b[i - 1]) <= k) f[i][0] |= f[i - 1][1];if (abs(b[i] - a[i - 1]) <= k) f[i][1] |= f[i - 1][0];if (abs(b[i] - b[i - 1]) <= k) f[i][1] |= f[i - 1][1];}cout << ((f[n][0] || f[n][1]) ? "Yes" : "No") << endl;
}