第一次在题库里刷到 P1006 传纸条 的时候，我的第一反应是：这不就是求两条路径的最大权值和吗？直接贪心先找一条最优路径，再找第二条不就行了。直到自己动手写了一版贪心，发现样例都过不了。第一条路走完，第二条路被挤在角落里，两个“局部最优”加起来远不是全局最优。后来去翻各种题解，看到“双状态DP”这个说法才意识到，这道题真正要学的不是路径搜索，而是怎么把“两个人同时移动”这个瞬间状态合理地编码进DP数组。这道题在很多算法题库里都有，适合刚学完区间DP、准备进阶网格DP的读者，也适合想搞清楚“为什么四维能压成三维”的人。下面我把整个推导、踩坑和代码实现完整梳理一遍。

1. 一张纸条怎么变成了两条不重合的路径

1.1 传纸条故事的模型化

题目背景是 m 行 n 列的座位矩阵，每个格子里有一个同学，每个同学有一个“好感度”数值。纸条从左上角传出，沿着只能向右或向下的方向，经过若干同学后到达右下角；然后还要从右下角原路传回左上角。整个过程中，除了起点和终点，同一个同学不能被重复传递。

把“传过去再传回来”翻译成算法语言时，大多数人会犯一个方向上的思维定式：去程是从左上到右下，回程是从右下到左上，方向相反，看起来得设计两套状态。

关键转换在于：把回程路径沿着时间倒过来看。一条从右下到左上的路径，倒序之后就变成一条从左上到右下的路径。也就是说，去程和回程可以统一成两条从左上角到右下角、方向完全一致的路径。题目里的“不能重复经过同一个同学”就变成：这两条路径除了起点和终点之外，不能共享任何格子。

这一步模型抽象是整个题目的地基。很多题解直接说“两条路径”，但没有解释为什么能这样等价转换。我在第一次做的时候，就是因为没想通方向问题，一直纠结要不要分别记录两条路径的方向，走了不少弯路。

1.2 为什么“先找一条最优路再找第二条”会翻车

既然变成了两条路径，一个很自然的想法是分两步做：先用最短路/DP找出权值和最大的一条路径，把这条路径上的格子标记为不可用，再找第二条。这种贪心思路在不少题目里都能用，但在传纸条这里会翻车。

原因很简单：第一条路径取了全局最优，但它可能把整个矩阵里“枢纽位置”的格子全部占掉，导致第二条路径只能绕很远的路，收益断崖式下降。局部最优的两段拼起来，并不等于整体最优。举个例子，矩阵中间有一个高权值格子，两条路径本来可以分别从它的两侧绕过，让总收益覆盖更多格子；但贪心会让第一条路径直接踩过这个高权值格子，第二条就被迫绕到边缘，整体收益反而不如两条路径都稍微“弯腰”的方案。

所以传纸条不能拆成两个独立子问题，必须把两条路径当成一个整体，在同一套状态里同步规划。这也是双状态DP必须“同步”的根本原因。

2. 状态设计：四维坐标为什么能砍成三个数

2.1 从四维DP出发

如果完全不考虑优化，最直觉的状态设计是四维：dp[i][j][k][l] 表示第一条路走到了 (i,j)，第二条路走到了 (k,l) 时，已经累计的最大权值和。转移时，每个人都可以从上方或左方过来，组合起来就是四种前驱：

• 第一条从上方，第二条从上方；
• 第一条从上方，第二条从左方；
• 第一条从左方，第二条从上方；
• 第一条从左方，第二条从左方。

这个模型本身是自洽的，m、n 最多 50 时，四维状态数约 50^4 = 625 万，勉强也能跑。但它有两个问题：一是浪费了大量不可能出现的状态，二是判重逻辑非常别扭——我并不知道两人是不是“先后”经过了同一个格子。

真正让我决定放弃四维写法的，是代码里那个判重：想判断两条路径有没有共享某个格子，得把整条路径的历史信息都记住才行。显然这不适合用 DP 解决。

2.2 同步不变量：行+列相等

四维DP最大的漏洞，是它没有利用“两个人同时出发、每步都走一格”这个条件。设当前两人都已经走了 s-1 步（也可以定义走了 s 步），时间是一致的。因为每步只能向右或向下，所以第一个人所在格子的行加列永远等于第二个人所在格子的行加列，这个公共值就是当前时刻的“步数指针”：

i + j = k + l = s

既然行加列恒定，那么四个坐标里其实只有三个自由度。知道 s 和某人的行坐标，就能算出他的列坐标。于是状态可以缩成三维：dp[s][i][k]，s 表示当前的行列之和，i 是第一个人的行坐标，k 是第二个人的行坐标。两个人的列坐标分别由 s-i 和 s-k 推导出来。

这个压缩没有丢失任何信息。因为路径只允许向右或向下，合法位置的坐标始终满足行加列等于固定值，不存在需要额外记住列坐标才能区分的歧义状态。

2.3 压缩带来的额外好处：判重变简单

压缩不只是省空间，它让“判断两人是否站在同一格”这件事变得极其简单。在同一个 s 时刻，如果两个人的行坐标相同，也就是 i == k，那么他们的列坐标也必然相同：

s - i = s - k

这意味着两人当前站在同一个格子里。于是“两条路径不能共享格子”这个条件，在同步DP里被翻译成一句非常干净的代码：当 i == k 且 s != m+n 时，这个状态非法，直接跳过。起点和终点允许两人相遇，所以单独放行终点即可。

我在理解这个判重时最大的感慨是：状态的压缩顺序应该反过来想。不是因为要压缩才故意选三维，而是因为发现了“行加列相等”这个不变量，三维状态本来就是问题内在的结构。用合适的坐标系描述问题，很多边界条件会自动变得清晰。

3. 四条前驱分支：递推式从哪来，边界怎么卡

3.1 上一步的四种来源

现在推导转移方程。dp[s][i][k] 表示当前两个人分别在 (i, s-i) 和 (k, s-k)。回到上一时刻 s-1，看第一个人这一步做了什么：

• 如果这一步向右走，行坐标不变，上一步行坐标仍然为 i，列坐标为 (s-1)-i；
• 如果这一步向下走，行坐标加 1，上一步行坐标就是 i-1，列坐标为 (s-1)-(i-1)=s-i。

第二个人同理，上一步行坐标要么是 k，要么是 k-1。把两个人的选择组合起来，得到四个前驱状态：

dp[s-1][i][k]、dp[s-1][i-1][k]、dp[s-1][i][k-1]、dp[s-1][i-1][k-1]

取这四个值的最大值，加上当前位置的权值，就是 dp[s][i][k]。

这里我用的行坐标是 r，代码里写作 r1、r2。如果你习惯用列坐标写，推导完全对称，但一定要全程保持一致，不要在同一个程序里混用行坐标和列坐标，否则很容易在中途把索引写乱。

3.2 权值累加与同格判重

当前位置的权值贡献分为两种情况。正常情况下，第一个人落在 (i, s-i)，第二个人落在 (k, s-k)，贡献为 a[i][s-i] + a[k][s-k]。但 i == k 时两人站在同一格，必须只计一次。

于是完整转移可以写成：

val = a[i][s-i] if (i != k) val += a[k][s-k] dp[s][i][k] = max(前四个前驱) + val

再加上一条合法性过滤：如果 i == k 且 s != m+n，说明两人在中间某个格子碰头了，这个状态非法。不过要注意，起点在 s=2 时已经初始化，且 s=m+n 的终点是合法碰头点，过滤时不能把终点也干掉。

很多人会把“重合时只计一次”和“重合时直接跳过”搞混。前者是方格取数的逻辑，后者才是传纸条的逻辑。传纸条里两人中间碰头就是非法，不是少计一次权值的问题，是整条路径都不能要。

3.3 为什么不需要担心“先后踏进同一个格子”

这是最容易被追问，也是最值得展开的一点。同步DP里的判重只检查了同一时刻两人是否站在同一格，那如果第一条路径先经过格子 P，第二条路径后经过格子 P，这算不算路径相交？会不会被漏掉？

答案是：这种方案确实在同步DP里不会被直接发现，但它不影响答案。原因是一条经典的重排定理：如果两条从左上到右下的路径在某个格子 P 相交，那么在 P 点之后，把第一条路径的后半段和第二条路径的后半段互换，得到的两条新路径仍然都是从左上到右下、只向右向下走的合法路径。P 之后的路径段长度是固定的，互换后总权值完全不变，但公共格的数量会减少。

重复这个交换过程，最后一定能得到一组除起点终点外互不相交的路径，而且权值不劣于原方案。既然存在一组最优解中的两条路径互不相交，那么同步DP只需枚举“任何时刻都不在同一格”的路径组，就能覆盖最优答案。这个结论是传纸条、方格取数这类题能用同步DP的理论基础。

3.4 用手算小例子验证逻辑

光讲公式容易飘，我用一个 3x3 的矩阵做个局部演算。矩阵如下：

1 2 3 4 5 6 7 8 9

s=2 时，只有 dp[2][1][1] = 1，也就是两个人都站在起点 (1,1)，权值只计一次。

s=3 时，行的合法范围是 1 到 2（因为行加列等于 3）。合法转移有两个：

• dp[3][1][2]：第一个人 (1,2)、第二个人 (2,1)，权值 = 1 + 2 + 4 = 7；
• dp[3][2][1]：权值也是 7，对称。

i==k 的 (1,1) 和 (2,2) 状态全被跳过。这两个 7 会继续参与 s=4 的计算，后面每层都只从四个前驱中取最大值扩展。这样一个简单例子就能确认坐标换算、前驱枚举和判重逻辑没有跑偏。

4. 完整代码与四个容易踩碎的细节

4.1 三维DP的标准写法

我习惯把行坐标记作 r，列坐标通过 s-r 算出。完整代码贴在下面，注释写的是最容易踩坑的位置：

#include <bits/stdc++.h> using namespace std; const int N = 55; const int INF = 0x3f3f3f3f; int a[N][N]; int dp[N * 2][N][N]; int main() { int m, n; cin >> m >> n; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j]; memset(dp, -INF, sizeof(dp)); // s = 2 对应两个人都站在起点 (1, 1) // 起点的权值只计一次 dp[2][1][1] = a[1][1]; for (int s = 3; s <= m + n; ++s) { // 行 r 的合法范围由 1 <= s - r <= n 推出 int r_lo = max(1, s - n); int r_hi = min(m, s - 1); for (int r1 = r_lo; r1 <= r_hi; ++r1) { for (int r2 = r_lo; r2 <= r_hi; ++r2) { // 中间碰头非法，终点允许碰头 if (r1 == r2 && s != m + n) continue; int c1 = s - r1; int c2 = s - r2; // 当前位置权值，重叠格只计一次 int val = a[r1][c1]; if (r1 != r2) val += a[r2][c2]; // 四条前驱分支 int best = dp[s - 1][r1][r2]; best = max(best, dp[s - 1][r1 - 1][r2]); best = max(best, dp[s - 1][r1][r2 - 1]); best = max(best, dp[s - 1][r1 - 1][r2 - 1]); dp[s][r1][r2] = best + val; } } } // 终点是 (m, n)，s = m + n，两人的行坐标都是 m cout << dp[m + n][m][m] << endl; return 0; }

代码里最需要注意的一点是 r_lo 和 r_hi 的推导。很多人图省事直接写成 1 到 m，然后靠里面的 if 判断越界，也能过，但那种写法容易读着读着就忘记自己还开着越界保护。我更推荐把循环边界直接卡对，这样后面加滚动数组时也更不容易出错。

4.2 滚动数组优化后的写法

三维版本的 dp 数组大小约 100 * 50 * 50，其实不算大。但如果 m、n 继续增大，或者以后遇到类似的三维网格DP，滚动数组就是必须掌握的技巧。观察转移可以发现，dp[s] 只依赖 dp[s-1]，更早的层永远不会再用到，所以可以只保留两层：

int dp[2][N][N]; // cur 表示当前层 int cur = 0; memset(dp, -INF, sizeof(dp)); dp[cur][1][1] = a[1][1]; // s = 2 for (int s = 3; s <= m + n; ++s) { int nxt = cur ^ 1; memset(dp[nxt], -INF, sizeof(dp[nxt])); int r_lo = max(1, s - n); int r_hi = min(m, s - 1); for (int r1 = r_lo; r1 <= r_hi; ++r1) { for (int r2 = r_lo; r2 <= r_hi; ++r2) { if (r1 == r2 && s != m + n) continue; int c1 = s - r1; int c2 = s - r2; int val = a[r1][c1]; if (r1 != r2) val += a[r2][c2]; int best = dp[cur][r1][r2]; best = max(best, dp[cur][r1 - 1][r2]); best = max(best, dp[cur][r1][r2 - 1]); best = max(best, dp[cur][r1 - 1][r2 - 1]); dp[nxt][r1][r2] = best + val; } } cur = nxt; } cout << dp[cur][m][m] << endl;

滚动数组的核心是每层开始前必须把目标层全部重置为负无穷。如果不重置，上一层残留的旧值会被新层读到，导致计算出不存在的路径。这个 bug 非常隐蔽，肉眼看不出来，只能靠造数据对比三维版和滚动版结果才能发现。

4.3 踩坑清单：四个常见错误

我把实际写代码过程中踩过、以及帮别人排查过的几个高频 bug 列在这里。

第一个是循环起点错。dp[2][1][1] 必须单独初始化，然后 for 循环从 s=3 开始。如果把 s=2 也放进循环里，又写了 r1==r2 时 continue，那么起点状态会被直接跳过，整个 DP 从一开始就全是负无穷，答案必然错。每当你发现代码输出一个非常大的负数，先检查初始化。

第二个是行范围写错。r 的范围不是 1 到 m，而是要满足列坐标 s-r 落在 1 到 n 之间，所以是 max(1, s-n) 到 min(m, s-1)。写错范围后，要么越界访问，要么把非法位置当成合法位置计算，答案会莫名偏大。

第三个是终点的权值。终点是唯一允许 r1 == r2 的普通同格状态（起点也允许但已经单独初始化了），此时 a[m][n] 必须只算一次。代码里我用 if (r1 != r2) val += a[r2][c2] 来保证，注意千万不要在终点加两次。

第四个是滚动数组不清空。这个前面已经提过，目标层必须 memset 回负无穷。另一个相关小问题是负无穷的取值，用 -0x3f3f3f3f 而不是 int 的最小值，否则加一个正权值就可能溢出成奇怪的正数。

4.4 验证思路

写完代码后，我一般不会只跑官方样例就收工。传纸条这种二维网格DP，最怕的是判重逻辑在某个边界偷偷失效。我的验证套路是：先用暴力搜索枚举所有合法路径组合，在小矩阵上跟 DP 结果对拍；确认无误后，再用随机矩阵跑三维版和滚动版，对比两者输出是否完全一致。

对拍脚本其实很简单，暴力 DFS 在 m、n 不超过 6 的时候完全跑得动。把 DP 答案和暴力答案逐一比较，能一次性发现绝大多数状态设计错误。这个习惯帮我排过很多次“样例过了但 WA”的冤案。

5. 从传纸条到方格取数：双状态DP还能套在哪

5.1 和方格取数只差一个判重

很多人第一次接触双状态DP是从方格取数那道经典题开始的，它和传纸条是天然的姐妹题。方格取数的题意也是两条从左上到右下的路径，但两条路径允许相交或重叠，只是重叠格子里的数字只计一次。传纸条则是直接禁止相交。

两题的代码几乎可以互相改：传纸条代码里那行“r1 == r2 且非终点就 continue”的逻辑，在方格取数里变成“r1 == r2 时只加一次权值，但不跳过”。反过来，方格取数代码加上一行中间碰头跳过，就变成传纸条。理解了这一点，两道题等于一起复习了。

我用一个简单对比表记录两者的核心差异：

5.2 障碍物、三人副本与不可压缩场景

如果题目在矩阵里加入障碍物，比如某些格子不能走，处理方式是把这些格子的权值设为负无穷，并在转移前判断当前位置是否合法。更严谨的做法是状态里根本不进入这些格子，直接把对应 dp 值留在负无穷。

如果题目从两个人升级成三个人传纸条，三条路径需要同时规划，状态就变成 dp[s][r1][r2][r3]，四个维度，行加列仍等于公共步数 s。状态数变成 O((m+n) * m^3)，在 m、n 较小的数据范围下依然可行。判重逻辑也相应扩展成三个行坐标两两不能相等。

需要警惕的是，双状态DP不是万能的。它的核心前提是“多个角色的移动步数永远相同”。如果题目允许某个人在某一步停留，或者路径可以走回头路，那么行加列相等这个不变量就被破坏了，必须回到更一般的高维状态，或者换成分层图模型。判断一道题能不能用“总步数+若干坐标”压缩，只需要看每个角色的每步移动是否都严格消耗一个单位时间、且方向单调。

我自己在实际做题中还有一个习惯：拿到网格DP先不急着写代码，先手写算几个小状态，确认坐标换算公式。传纸条这道题最精彩的地方在于，它把“同步时钟”这个抽象概念落到了非常具体的网格上。一旦想通两个人是在同一排秒针里移动，三维状态、四路转移、碰头判重这些细节就全部变得顺理成章。希望这篇梳理能帮你少走一点我当时走过的弯路。