第一次在题库里刷到 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 ! mn 时这个状态非法直接跳过。起点和终点允许两人相遇所以单独放行终点即可。我在理解这个判重时最大的感慨是状态的压缩顺序应该反过来想。不是因为要压缩才故意选三维而是因为发现了“行加列相等”这个不变量三维状态本来就是问题内在的结构。用合适的坐标系描述问题很多边界条件会自动变得清晰。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 ! mn说明两人在中间某个格子碰头了这个状态非法。不过要注意起点在 s2 时已经初始化且 smn 的终点是合法碰头点过滤时不能把终点也干掉。很多人会把“重合时只计一次”和“重合时直接跳过”搞混。前者是方格取数的逻辑后者才是传纸条的逻辑。传纸条里两人中间碰头就是非法不是少计一次权值的问题是整条路径都不能要。3.3 为什么不需要担心“先后踏进同一个格子”这是最容易被追问也是最值得展开的一点。同步DP里的判重只检查了同一时刻两人是否站在同一格那如果第一条路径先经过格子 P第二条路径后经过格子 P这算不算路径相交会不会被漏掉答案是这种方案确实在同步DP里不会被直接发现但它不影响答案。原因是一条经典的重排定理如果两条从左上到右下的路径在某个格子 P 相交那么在 P 点之后把第一条路径的后半段和第二条路径的后半段互换得到的两条新路径仍然都是从左上到右下、只向右向下走的合法路径。P 之后的路径段长度是固定的互换后总权值完全不变但公共格的数量会减少。重复这个交换过程最后一定能得到一组除起点终点外互不相交的路径而且权值不劣于原方案。既然存在一组最优解中的两条路径互不相交那么同步DP只需枚举“任何时刻都不在同一格”的路径组就能覆盖最优答案。这个结论是传纸条、方格取数这类题能用同步DP的理论基础。3.4 用手算小例子验证逻辑光讲公式容易飘我用一个 3x3 的矩阵做个局部演算。矩阵如下1 2 3 4 5 6 7 8 9s2 时只有 dp[2][1][1] 1也就是两个人都站在起点 (1,1)权值只计一次。s3 时行的合法范围是 1 到 2因为行加列等于 3。合法转移有两个dp[3][1][2]第一个人 (1,2)、第二个人 (2,1)权值 1 2 4 7dp[3][2][1]权值也是 7对称。ik 的 (1,1) 和 (2,2) 状态全被跳过。这两个 7 会继续参与 s4 的计算后面每层都只从四个前驱中取最大值扩展。这样一个简单例子就能确认坐标换算、前驱枚举和判重逻辑没有跑偏。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 循环从 s3 开始。如果把 s2 也放进循环里又写了 r1r2 时 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 时只加一次权值但不跳过”。反过来方格取数代码加上一行中间碰头跳过就变成传纸条。理解了这一点两道题等于一起复习了。我用一个简单对比表记录两者的核心差异题目两条路径能否共享中间格子判重处理方式DP思路传纸条不能r1r2 且非终点时直接跳过同步三维DP方格取数可以但共享格只计一次r1r2 时权值只加一次同步三维DP5.2 障碍物、三人副本与不可压缩场景如果题目在矩阵里加入障碍物比如某些格子不能走处理方式是把这些格子的权值设为负无穷并在转移前判断当前位置是否合法。更严谨的做法是状态里根本不进入这些格子直接把对应 dp 值留在负无穷。如果题目从两个人升级成三个人传纸条三条路径需要同时规划状态就变成 dp[s][r1][r2][r3]四个维度行加列仍等于公共步数 s。状态数变成 O((mn) * m^3)在 m、n 较小的数据范围下依然可行。判重逻辑也相应扩展成三个行坐标两两不能相等。需要警惕的是双状态DP不是万能的。它的核心前提是“多个角色的移动步数永远相同”。如果题目允许某个人在某一步停留或者路径可以走回头路那么行加列相等这个不变量就被破坏了必须回到更一般的高维状态或者换成分层图模型。判断一道题能不能用“总步数若干坐标”压缩只需要看每个角色的每步移动是否都严格消耗一个单位时间、且方向单调。我自己在实际做题中还有一个习惯拿到网格DP先不急着写代码先手写算几个小状态确认坐标换算公式。传纸条这道题最精彩的地方在于它把“同步时钟”这个抽象概念落到了非常具体的网格上。一旦想通两个人是在同一排秒针里移动三维状态、四路转移、碰头判重这些细节就全部变得顺理成章。希望这篇梳理能帮你少走一点我当时走过的弯路。