A
定义 \(f_{i}\) 为跳到第 \(i\) 格的最小 cost。
跳出一步后的子问题和跳出一步前的子问题基本相同，只不过一个跳到 \(i-1\) 一个跳到 \(i\)，则有
，其中 \(c_{i,j}\) 代表从 \(i\) 跳到 \(j\) 的 cost。
B
类似 A，不再分析。
\[f_i = \min\{f_{i-x} + c_{i-x, i} \mid x \in [1, k]\} \]C
定义 \(f_{i,j}\) 为第 \(i\) 天，这次的活动为 \(j\)，最大的幸福。
\[f_{i,j} = \max\{f_{i-1,x} + h_{i,j} \mid x \ne j \} \]D
定义 \(f_{i,j}\) 为前 \(i\) 个物品达到 \(\le j\) 容量的最大价值。
\[f_{i,j} = \max\{f_{i-1, j-w_i}+v_i,f_{i-1,j}\} \]E
定义 \(f_{i,j}\) 为前 \(i\) 个物品达到 \(\ge j\) 容量的最小重量。
\[f_{i,j} = \min\{f_{i-1, j-v_i}+w_i,f_{i-1,j}\} \]F
定义 \(f_{i,j}\) 为第 \(S_{i..}\) 匹配 \(T_{j..}\) 的最大长度，有状态转移方程
\[f_{i,j} = \max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+1 \text{ if } S_i = T_j\} \]得到 LCS 长度后，通过看转移方程的三项的哪一项与本格来判断通过哪路，来进行计算，即可解决。
G
设题面给出的图为 \(G\)，建出反图 \(G'\)，在 \(G\) 上跑 topsort，得到 \(A\)，在 \(A\) 上进行 dp。
定义 \(f_i\) 为 \(1 \to i\) 的最长路的长度，有 \(f_i = \max\{f_x \mid x \in G'_i\} + 1\)
正确性证明：枚举的 \(x\) 就是一条边 \(x \to i\)，在反图 \(G'\) 上表现为 \(i \to x\)
H
定义 \(f_{i,j}\) 为 \((1,1) \to (i,j)\) 的路径条数，则有
\(f_{i,j} = \left\{\begin{matrix}0 & m_{i,j} = \texttt{#} \\ f_{i-1,j} + f_{i,j-1} & \text{otherwise}\end{matrix}\right.\)
I
定义 \(f_{i,j}\) 为 \(i\) 个硬币投出 \(j\) 个正面的概率。
首先求出 \(f_{i,0} = f_{i-1,0} \times (1-p_i)\)，然后有决策这个是正面还是反面，则有
。
J1
因为盘子的顺序不影响期望，所以直接把它压缩到 \(4\) 维，\(f_{w_0,w_1,w_2,w_3}\) 代表有 \(w_i\) 盘 \(i\) 个（$i \in [0,3]），状态转移为
\[f_{w_0,w_1,w_2,w_3} = (1-\dfrac{w_0}{n}) \times (1+f_{w_0+1,w_1-1,w_2,w_3}\times\dfrac{w_1}{n}+f_{w_0,w_1+1,w_2-1,w_3}\times\dfrac{w_2}{n}+f_{w_0,w_1,w_2+1,w_3-1}\times\dfrac{w_3}{n}) \]J2
发现 \(w_0\) 几乎没用，而且 \(1-\dfrac{w_0}{n} = \dfrac{w_1+w_2+w_3}{n}\)，于是可以直接缩掉这一维 dp。
K
定义 \(f_i\) 为有 \(i\) 个石子的时候谁赢。
先手具有游戏控制权，所以只要有一种取石子的方案使得取完石子是轮到谁谁输的方案（此时轮到后手），则先手赢。
可以定义 \(0\) 为轮到谁谁赢，\(1\) 为轮到谁谁输（\(\lor\) 为逻辑或，\(\lnot\) 为逻辑非），则有
。
L
注意到 \(X+Y\) 是定值，而 \(X-Y=X+Y-2Y\)，也就是说 最大化 \(X-Y\) 就是最小化 \(Y\)，最小化 \(X-Y\) 就是最大化 \(Y\)。
而左右出队相当于区间 \(L\) 左移或 \(R\) 右移，所以考虑区间 dp。
\(f_{L,R,s}\) 代表了 \([L,R]\) 区间内轮到 \(s\) 的最优 \(Y\)（最优就是 \(s\) 对应的最大/最小）。
只统计 \(Y\) 的分数，就可以 DP 了。
M1
定义 $f_{i,j} = $ 前 \(i\) 人一共 \(j\) 个蜡烛的方案数，则有
\[f_{i,j} = \sum_{g=0}^{\min(j,a_i)} f_{i-1,j-g} \]。
M2
发现转移出的 \(f_{i-1,[j, j-\min(j,a_i)]}\) 是一个区间，可以直接使用前缀和进行优化，定义
\[s_{i,j} = \sum^j_{k=0} f_{i,k} \]，则有
\[f_{i,j} = s_{i-1,j} - s_{i-1,j-\min(j,a_i)-1} \]。
N
将 \([l,r]\) 合并成一块可以分裂为 \([l,m]\) 和 \([m+1,r]\) 做一次合并操作，于是定义 \(f_{i,j} = [i, j]\) 合并成一块的最小代价，且本次的代价一定是 \(\sum a_{[i,j]]\)，则有
\[f_{l,r} = \min\limits_{m=l+1}^{r-1} f_{l,m} + f_{m+1, r} + \sum a_{[l,r]} \]。
O
定义 \(f_S\) 为 \(S\) 这个集合里面的所有人配对的方案数，则有
\[f_S = \sum f_{S - \{x\}} : x \in S \wedge a_{|S|,x} \]。
P
定义 \(f_x\) 为 \(x\) 是黑色的可能总数，\(g_x\) 为 \(x\) 是白色的可能总数。
\[f_x = \prod g_y : y \in S_x; g_x = \prod (f_y + g_y) : y \in S_x \]。
Q1
定义 \(f_i\) 为前 \(i\) 朵花满足条件的 max beauty，有
\[f_i = \max\limits_{j=1}^{i-1}\{f_j : h_j < h_i\} \]。
Q2
发现有 \(j<i \wedge h_i<h_j\)，考虑一个数组，其下标为 \(h\)，值为 \(a\)，问题转化为单点修改，前缀 \(\max\)，可以使用树状数组解决。
R1
暴力 DP，定义 \(f_{i,L,R}\) 为走了 \(i\) 步，\(L \to R\) 的路径总数，像 G 一样建出返图 \(G'\)，得到
\[f_{i,L,R} = \sum (f_{i-1,L,x} : x \in G_R') \]R2
把上面的柿子换个写法，令邻接矩阵为 \(A\)，则有
\[f_{i,L,R} = \sum f_{i-1,L,x} \times A_{x,R} \]，构成矩阵乘法（\(f_{i} = f_{i-1} \times A\)），可以矩阵快速幂求 \(A^K\)。
S
定义 \(f_{i,j,k}\) 为 \([1,(j+1) \times 10^{i-1} - 1]\) 中有数位和 \(\bmod D = k\) 的数的数目，有
\[f_{i,j,k} = f_{i,j-1,k}\text{（开头不是 $j$）} + f_{i-1,9,k-j}\text{（开头是 $j$）}+ [j \bmod D = k]\text{（正好是 $j \times 10^{i-1}$）} \]T1
定义 \(f_{i,j}\) 为前 \(i\) 个数，最后一个数在排列中是第 \(j\) 小的方案数。
\[f_{i,j} = \left\{\begin{matrix}\sum\limits_{x=1}^{j-1} f_{i-1,x} & S_i = \texttt{<} \\ \sum\limits_{x=j}^{i} f_{i-1,x} & S_i = \texttt{>}\end{matrix}\right.\]T2
发现 T1 的状态转移构成区间和，所以考虑前缀和 dp。
U
定义 \(C_S = \dfrac 12\sum\limits_{x \in S} \sum\limits_{y \in S} a_{x,y}\)，定义 \(f_S\) 为 \(S\) 划分出的最大收益，于是有
\[f_S = \max\{C_{T} + f_{S - T} \mid T \subseteq S\} \]，预处理出所有的 \(C\) 就可以解决。