多维 DP

三扔硬币

状态为 $f_{i,0/1,0/1}$ ，表示：前 $i$ 枚硬币，第 $i$ 枚的状态是 $0/1$，第 $i-1$ 枚的状态是 $0/1$ 的方案数。

根据这个状态，就可以从 $f_{i-1,0/1,0/1}$ 这一维度的状态轻松转移，因为 $i-1$ 这一维度后面两个维度就分别代表了第 $i-1$ 枚和第 $i-2$ 枚硬币的情况。

状态转移如下：

$$\begin{cases} f_{i,0,0}=f_{i-1,0,1}\\ f_{i,0,1}=f_{i-1,1,0}+f_{i-1,1,1}\\ f_{i,1,0}=f_{i-1,0,1}+f_{i-1,0,0}\\ f_{i,1,1}=f_{i-1,1,0} \end{cases}$$

答案为 $\sum\limits_{j=0}^1\sum\limits_{k=0}^1 f_{n,j,k}$，其实就是 $f_{n,0,0}+f_{n,0,1}+f_{n,1,0}+f_{n,1,1}$。

其余细节：

• 注意初始化问题，根据状态设计这个状态必须得有至少两枚硬币才能做。
• 因此初始化 $f_{2,0,0}=f_{2,0,1}=f_{2,1,0}=f_{2,1,1}=1$，那么当 $n=1$ 特判一下输出即可。

数字三角形

状态设计

$f_{i,j}$ 为走到点 $i,j$ 的最大值

状态转移

走到点 $(i,j)$ 只能由 $(i-1,j)$ 或 $(i-1,j-1)$ 走过来即

$$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1})+a_{i,j}$$

其余细节

由于最终并未规定走到最后一行的哪个点，所以对所有可能的位置求 $\max$ 即可

三倍经验

状态设计

$f_{i,j,k}$ 为走到点 $(i,j)$ 且目前乘 $3$ 次数已经用了 $k$ 次的最大值。

状态转移

首先走到点 $(i,j)$ 必然是由 $(i-1,j)$ 或 $(i-1,j-1)$ 走过来的，其次在点 $(i,j)$ 还可以考虑是否让当前 $(i,j)$ 这个数字乘以 $3$ 所以一共有 $4$ 种转移的情况。

$$\begin{aligned} f_{i,j,k}&=\max(f_{i,j,k},f_{i-1,j,k}+a_{i,j})\\ f_{i,j,k}&=\max(f_{i,j,k},f_{i-1,j,k-1}+a_{i,j}\times 3),k\not= 0\\ f_{i,j,k}&=\max(f_{i,j,k},f_{i-1,j-1,k}+a_{i,j})\\ f_{i,j,k}&=\max(f_{i,j,k},f_{i-1,j-1,k-1}+a_{i,j}\times 3),k\not= 0\\ \end{aligned}$$

其中前两个转移对应的是从上方走过来，后两个对应从左上方走过来。

其余细节

• 走到第 $n$ 行以后，也不一定把乘 $3$ 次数用完，所以要对第 $n$ 行所有位置的所有状态求 $\max$
• 初始 $f_{i,j,k}$ 都为一个极小值，因为题目数据范围有负数，$f_{1,1,0}=a_{1,1},f_{1,1,1}=a_{1,1}\times 3$
• 注意开 long long。由于一行只能选择一个数字，所以 $m$ 可以和 $n$ 取 $\min$。

方格取数

走 $2$ 次，然后求取得的数字最大和。可以看成两个人一起出发去走的最大和。

状态设计

$f_{x_1,y_1,x_2,y_2}$ 为第一个人走到 $(x_1,y_1)$ ，第二个人走到 $(x_2,y_2)$ 的数字最大和。

状态转移

转移分 $4$ 种情况（第一个人由上方或左边过来，第二个人由上或左过来。$2*2=4$ 种）。且如果走到同一个点，数字只能相加一次。

其余细节

注意两个人走到同一个位置只计算一次答案。

[CSP-J 2022] 上升点列

注意到可以添加 $k$ 个自由点，因此两个点 $i,j$ 之间的曼哈顿距离 $\leq k+1$ 是极限。也就是说将来答案一定可以用到这 $k$ 个点，因此正常求出最长的二维递增子序列的最大长度，给答案加 $k$ 即可。

• 状态设计：定义 $f_{i,k}$ 为以 $i$ 结尾用了 $k$ 个自由点的最大长度。
• 状态转移：枚举上一个点 $j$，计算二者之间的距离曼哈顿距离记为 $d$。若满足 $d\geq k+1$ 则可以转移。由 $f_{j,k-d-1}$ 转移，它们之间用掉 $d-1$ 个自由点。

注意排序。

最长公共上升子序列

本题的状态设计融合了公共子序列和上升子序列。

状态设计：$f_{i,j}$ 为以 $a$ 的前 $i$ 个数， $b$ 的前 $j$ 个数字且以 $b_j$ 结尾的最长公共上升子序列的长度。

状态转移

• $f_{i,j}=f_{i-1,j}$ 此举为不包含 $a$ 的第 $i$ 个元素。
• 如果包含 $a_i$, 首先必须满足 $a_i=b_j$，那么根据最长上升子序列的转移，我们还要枚举 $b_j$ 前面的某个元素，从它转移过来。
  • 即 $f_{i,j}=\max(f_{i,j},f_{i-1,k}+1),a_i>b_k$

字串距离

和编辑距离非常相似，设计 $f_{i,j}$ 为 $s$ 的前 $i$ 个字符和 $t$ 的前 $j$ 个字符相等后的最小值。