P1006 传纸条我第一次见是在一份动态规划题单里题目包装得很校园你传我、我传你中间每个格子还标着善意值。剥掉故事外壳它其实是个需要把两条路径放在同一个 DP 状态里一起规划的双状态DP问题。很多做过“方格取数”的同学第一次写这题都会很自信结果交上去发现要么答案偏大要么直接 WA原因多半是没想透“两条路径同时走”意味着什么。这篇文章我从头推导一遍状态设计、转移方程、代码实现再把实际调题踩过的坑翻出来希望能让刷这道题的人少走点弯路。1. 这道题在问什么以及最容易掉的坑1.1 题目场景还原题面大概是这样有一个 n 行 m 列的矩阵每个格子有一个数值代表同学之间的善意值。现在要从左上角 (1,1) 的同学出发把一张纸条传到右下角 (n,m) 的同学手里对方看完之后还要再传回一张纸条。传纸条只能向右或向下移动每个格子上的同学最多只能帮忙传递一次所以两条路径不能在中间格子重合。要求两条路径经过的格子上的数值之和最大。这里有个容易误会的点题目里说的是“过去一条、回来一条”但二维网格里的路径是可逆的。你把回程路径从 (n,m) 倒着看到 (1,1)本质上还是一条从起点到终点的路径。所以问题可以等价转换成选两条从 (1,1) 到 (n,m) 的路径中间不能相交让覆盖到的格子分值总和最大。起点和终点是两个路径共用的允许重合这个特判后面会反复用到。这类题的经典解法不是“分别规划”而是“同步规划”。什么叫同步规划就是想象两个人同时从左上角出发每一步一个人只能向右或向下走两个人的走动是同步的步数永远一样多。既然步数一样多那么同一时刻两个人在棋盘上的“行列和”一定相等。正是这个“行列和相等”的约束最后帮我们把 DP 状态从四维压到三维。1.2 为什么不能拆成两次普通 DP初学者最常见的想法是先用一次普通 DP 求出“第一条最优路径”然后把这条路径经过的格子分数清零再跑一次 DP 求第二条路径两次结果相加不就是答案吗这个思路看起来自然但它贪心了。第一次 DP 只保证第一条路单独最优完全不考虑这条路是否会堵死第二条路。数学上这破坏了动态规划的最优子结构每一步的最优决策不应该只依赖当前局部状态还要照顾另一条路径未来的空间。你可以自己构造一个小矩阵试试故意把高权值格放在一条窄通道上第一条路取走它之后第二条路只能被迫绕到全是低分的角落而如果第一条路稍微绕一下让出通道两条路的总分反而更高。这就是“分开两次 DP”会得到错误答案的核心原因。所以 P1006 这类题必须把两条路径放进同一个状态里让它们在时间轴上一起演进。这也是标题里“双状态DP”的真正含义。2. 双状态DP的状态设计逻辑2.1 用一条“对角线”当作时间轴先假设两条路径同时出发、同时走规定每一步只能向右或向下。设第一条路径当前在 (x1, y1)第二条路径当前在 (x2, y2)。因为同步走两个人从 (1,1) 出发经过的步数是一样的所以有x1 y1 x2 y2这个相等的“行列和”就是每条对角线上所有格子的共同编号。如果要遍历格子不需要同时关注 x 和 y只要知道当前在哪条对角线上再知道该路径当前在第几行列就唯一确定了。这个“行列和”就是时间轴我习惯用 s 表示。于是可以定义状态dp[s][x1][x2] 表示两条路径目前都位于行列和为 s 的对角线上第一条路径在第 x1 行列是 s - x1第二条路径在第 x2 行列是 s - x2时能取得的最大分值总和。单个路径的普通 DP状态里只需要一个当前点双状态DP状态里同时装着两个当前点。第一维 s 记录公共时间后两维 x1、x2 记录两个人的行坐标两个人的列坐标通过 s 减去行坐标得到。这就是“双状态”这个说法的来源表面上状态变量有三个维度但本质上同时管理两条路径的位置。2.2 为什么知道了行就能推列有人会问状态里为什么没有 y1 和 y2因为 s 定了行定了列就是 s - x。比如某条路径在 s 5 这一层行 x 2那列必然是 3。这要求在棋盘边界内合法也就是列必须在 1 到 m 之间。这个“由行列和反推列坐标”的操作是整道题最关键的压缩手段。你如果硬要用四维状态 dp[x1][y1][x2][y2] 也不是不行但那样状态数量会膨胀到 n²m²而且转移时还得考虑两条路径步数是否一致会很别扭。用对角线 s 之后的复杂度是 O((nm) * n²)在实际题目给定 n、m 都是几十到一百左右时运行压力很小代码也清爽很多。这里我想额外说一点做题直觉遇到“两个物体在网格上同步移动”的 DP优先找它们的“公共不变量”。在这题里公共不变量就是行列和在另一些题里可能是可移动步数可能是剩余体力。你把公共不变量找出来往往就能像削苹果一样把高维状态一层层削掉。3. 转移方程和“重叠格子”怎么处理3.1 四个前驱状态怎么来的当前状态是 dp[s][x1][x2]两条路径都走到了对角线 s。每条路径在进入当前格子之前只能来自上边或左边。第一条路径的上一步可能是 (x1 - 1, s - x1) 或 (x1, s - x1 - 1)第二条路径同理。两者组合起来上一层的状态一共有四种第一条从上边来第二条从上边来dp[s-1][x1-1][x2-1]第一条从上边来第二条从左边来dp[s-1][x1-1][x2]第一条从左边来第二条从上边来dp[s-1][x1][x2-1]第一条从左边来第二条从左边来dp[s-1][x1][x2]取这四个值的最大值再加上当前两条路径所在格子的数值就是 dp[s][x1][x2]。写成公式就是dp[s][x1][x2] max(上面四个前驱) 当前两个格子的分数这个转移本身不复杂。容易混的是第四个dp[s-1][x1][x2] 表示两条路径都从各自左边的格子走过来。由于层数从 s-1 变成 s行没变列各自加一完全符合向右走的规则。第一次写代码时容易漏掉这个组合导致答案偏小。3.2 两条路径走到同一个格子怎么办接下来是重头戏如果 x1 x2因为两格子在同一层 s 上列也必然相同也就是说两条路径当前走到了同一个格子。这时按题意中间格子是不能重复使用的所以这个状态应该视情况处理。当 s 2 时两个人都还在起点 (1,1)起点只能贡献一次分数当 s nm 时两个人都到达终点 (n,m)终点也只能贡献一次分数当 s 为中间值且 x1 x2 时两条路径重合了严格写法应该直接跳过这个非法状态。但你会发现很多网上题解在 x1 x2 时并不跳过而是只加一次该格子的分数。为什么这样也能过因为题目给出的格子善意值是非负的。如果两条路径在某个中间格重合它们扫过的格子集合和两条不相交路径扫过的集合在“路径可交换”的意义下是可以对齐的也就是说非负权值时允许重叠但只计一次分的最优值和强制不允许重叠的最优值是相等的。这个结论很多新手不知道看到代码里有个if (i j)的诡异分支容易以为写错了。我个人建议学习阶段先用“严格跳过中间重叠”的版本理解题意提交时用“重叠只计一次分数”的版本后者对 n1 或 m1 这种退化边界更友好。两种写法我都放在后面代码部分给出实现。4. 完整实现从三维 DP 到滚动数组4.1 可以直跑的三维对角 DP先给出一个最容易理解的版本用二维数组滚动也能跑但这里先展示带完整维度的写法方便对着状态定义看。下面代码以 n 行 m 列为例所有格子下标从 1 开始s 从 2 枚举到 n m。二维格子数值用变量名aDP 数组第一维直接用s展开#include bits/stdc.h using namespace std; const int N 55; const int INF 1e9; int n, m; int a[N][N]; int dp[N * 2][N][N]; int main() { cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } // 初始化所有状态为不可达 for (int s 0; s n m; s) { for (int i 0; i n; i) { for (int j 0; j n; j) { dp[s][i][j] -INF; } } } // s 2 时两条路径都只能在起点 (1,1) dp[2][1][1] a[1][1]; for (int s 3; s n m; s) { for (int x1 1; x1 n; x1) { for (int x2 1; x2 n; x2) { int y1 s - x1; int y2 s - x2; if (y1 1 || y1 m || y2 1 || y2 m) continue; int best dp[s - 1][x1][x2]; best max(best, dp[s - 1][x1 - 1][x2]); best max(best, dp[s - 1][x1][x2 - 1]); best max(best, dp[s - 1][x1 - 1][x2 - 1]); if (best -INF / 2) continue; if (x1 x2) { // 里程碑写法重叠只算一次 dp[s][x1][x2] best a[x1][y1]; } else { dp[s][x1][x2] best a[x1][y1] a[x2][y2]; } } } } cout dp[n m][n][n] endl; return 0; }这段代码的边界考虑是这样的起点已经在初始化时加过了所以循环从 s3 开始终点在同一格重叠分支只加一次 a[n][m]中间如果重叠因为是非负权值重复格子只计一次即可。最终答案存在 dp[n m][n][n]也就是两条路径都到达第 n 行时列分别是 m终点重合。4.2 滚动数组优化空间再降一个量级三维版本已经够用但竞赛题经常要养成节约空间的好习惯。因为第 s 层只依赖第 s - 1 层DP 的第一维只需要保留两个取值也就是dp[s 1]和dp[(s - 1) 1]。#include bits/stdc.h using namespace std; const int N 55; const int INF 1e9; int n, m; int a[N][N]; int dp[2][N][N]; int main() { cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) { for (int j 0; j n; j) { dp[0][i][j] dp[1][i][j] -INF; } } // s 2 这一层对应 parity 0 dp[0][1][1] a[1][1]; for (int s 3; s n m; s) { int now s 1; int pre (s - 1) 1; // 先清理当前层防止残留上一层的旧值 for (int i 0; i n; i) { for (int j 0; j n; j) { dp[now][i][j] -INF; } } for (int x1 1; x1 n; x1) { for (int x2 1; x2 n; x2) { int y1 s - x1; int y2 s - x2; if (y1 1 || y1 m || y2 1 || y2 m) continue; int best dp[pre][x1][x2]; best max(best, dp[pre][x1 - 1][x2]); best max(best, dp[pre][x1][x2 - 1]); best max(best, dp[pre][x1 - 1][x2 - 1]); if (best -INF / 2) continue; if (x1 x2) { dp[now][x1][x2] best a[x1][y1]; } else { dp[now][x1][x2] best a[x1][y1] a[x2][y2]; } } } } cout dp[(n m) 1][n][n] endl; return 0; }注意滚动数组最容易被坑的点不清空当前层或者把dp[now]里上一层的值直接拿来参与转移。因为你每次只保留两层但同一个位置的上一轮数据并不一定对应合法状态不清空就会污染答案。时间上s 从 2 到 nm每一层两层行循环总复杂度是 O((nm) * n * n)。空间上从三维变成了两个二维数组就是 O(n²)。这个优化在 P1006 这种小数据面前可能“锦上添花”但养成习惯后遇到 nm 更大的类似模型你就能直接套。5. 实战踩坑记录从 WA 到 AC 的几个关键点5.1 坐标合法性判断千万别漏y s - x是很容易算出负数或超过 m 的。很多人写循环时只遍历 x1、x2忘了检查 y1、y2 是否在 1 到 m 之间结果数组越界或者把非法状态当成合法状态转移。这题的格子强约束就是“列必须存在”所以每层循环一开始就把y1 1 || y1 m || y2 1 || y2 m过滤掉宁可靠前判断也别靠 DP 值自然填充。还有一个隐蔽问题当你用x1 - 1或x2 - 1作为索引访问上一层层时可能访问索引 0。如果 dp 数组第 0 行没有初始化为不可达它会读到一个垃圾值甚至可能导致错误更新。我的习惯是把 dp 数组第 0 行也统一初始化为 -INF代码里循环范围从 0 到 n 都清理一遍这样x1 - 1就算等于 0也只会读到不可达。5.2 初始化用 -INF不要用 0最大值 DP 里不可达状态必须和“合法但分数为 0”的状态区分开。如果初始值全部用 0那些从非法位置“虚空转移”出来的状态也会变成合法路径最终结果会凭空多出一大截。正确做法是用一个足够小的负数比如-1e9表示“这条路径不存在”。转移时再判断best -INF / 2就跳过。这里不要用0x3f3f3f3f那个是求最短路时的“正无穷”用在这里方向反了会表现得特别诡异。5.3 起点和终点的分数别重复加起点有两种处理方式一是先初始化dp[2][1][1] a[1][1]循环里不再加起点二是从 s2 开始把所有状态都通过转移计算但这样代码更难控制。终点同理当 x1 x2 时只加一次终点分。如果你发现自己的答案比预期多了一个格子的值先检查是不是初始化时加了起点转移时又因为重叠把起点加了一次。我调这题的时候曾经把输出写成dp[n m][n][n] a[n][m]结果总是多算一遍终点分。当时百思不解后来才反应过来终点重叠时代码里的if (x1 x2)分支已经加过 a[n][m] 了我输出又加一次当然错。5.4 边界情况 n1 或 m1 的特判思维如果棋盘只有一行或者一列从左上到右下只有一条路径两条路径被迫只能走同一条线。严格题意下这看起来没有合法解但 OJ 的数据一般不会让你真的输出一个无意义的东西而是会把这条唯一路径的分值算作答案。这就是为什么很多实现采用“重叠只加一次分数”而不是“中间重叠直接 continue”。直接跳过重叠的话n1 时所有中间状态全都非法答案会变成 -INF直接 WA。所以我在代码里用了重叠只计一次分数的写法而不是严格禁止重叠。如果你非常较真想写严格版本也可以在中间x1 x2时直接跳过但你必须确认题目的 n、m 数据保证至少存在两条不相交路径。就我实际刷题的经验来看比赛里绝大多数这种题权值非负允许重叠只算一次的写法更稳。6. 从传纸条带走的一点思考方式P1006 是我觉得双状态DP特别好的入门题因为它的故事简单状态压缩又很明显。我做这类题有一个习惯拿到题目先画一个网格把起点、终点和几条对角线标出来然后在纸上手动模拟几个状态。这个过程看着慢但能非常直观地理解“为什么 dp[s][x1][x2] 够用”。如果你后面遇到更复杂的双人移动问题比如两个人有不同速度、可以原地等待、或者允许相撞但代价不同不要急着套公式先回到建模的原点找公共时间轴找坐标之间的关系再把约束写进转移公式。传纸条这道题把“同步 不重叠”这个模型演示得很干净吃透它相当于给更复杂的双状态DP打了一个非常扎实的基础。最后再分享一个我自己的教训刷 DP 题不要只盯着 AC多花十分钟想一想“这个状态为什么可以压缩”“这个重叠分支为什么能这么写”。想明白之后下次遇到变体题你会比死记模板的人快很多。