AcWing1015. 摘花生

考虑读入时是从北向南，从西向东的，因此我们可以认为是按照$(1, 1), (1, 2), …, (n, m)$的
$f[i][j]$ 表示到达第i行第j列这个格子时可以获得的最大花生数
故状态转移方程为：$f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]$

code

AcWing1018. 最低通行费

$f[i][j]$ 表示到达第i行第j列这个格子时的最低通行费
故状态转移方程为：$f[i][j] = min(f[i - 1][j], f[i][j - 1]) + a[i][j]$

code

AcWing1017. 方格取数

$f[i_1][j_1][i_2][j_2]$表示第一次到达$(i_1, j_1)$，第二次到达$(i_2, j_2)$时的总数字和
由于一个格子的数只会被取一次，可以想到的是，当一个格子被到达两次时，其$i_1=j_1,i_2=j_2$
因此规定$i_1+j_1=i_2+j_2$，为$f[i_1][j_1][i_2][j_2]$的一个限制。
因此这里可以优化一维：$k=i_1+j_1 → f[i_1][j_1][k]，j_1=k-i_1,j_2=k-i_2$

状态转移：$f[i_1][i_2][k] = f[i_1-c][i_2-d][k-1]+a[i_1][k-i_1] + (i_1 \neq i_2) \times a[i_2][k-i_2]$
其中$0\leq c,d\leq 1$

code

AcWing275. 传纸条
$f[i_1][i_2][k]$表示第一次到达(i_1,k-i_1)，第二次到达(i_2,k-i_2)获得的最大好心程度和
由于一个同学不会帮忙传递两次，因此不允许交叉，即在中途不允许出现$i1\neq i_2$

同时边界有判断：可以放在循环内直接判$1\leq i_1\leq min(n, k), 1\leq j_1\leq min(m, k)$
或者先推导出$i_1$的左右边界即可。

状态转移：$f[i_1][i_2][k] = f[i_1-c][i_2-d][k-1]+a[i_1][k-i_1] + a[i_2][k-i_2]$
其中$0\leq c,d\leq 1$

code