动态规划解决方格取数问题：双人路径最优解

1. 问题背景与题目解析

"方格取数"是一道经典的动态规划题目，最初出现在2000年全国青少年信息学奥林匹克竞赛(NOIP)提高组的比赛中。这道题目考察的是在二维网格中进行路径规划时，如何高效计算最优解的能力。

题目描述大致如下：给定一个N×N的方格矩阵，每个格子中有一个正整数。现在有一个人从左上角(1,1)出发，每次只能向右或向下移动，最终到达右下角(N,N)。在移动过程中，经过的格子中的数字会被取走。题目要求计算从起点到终点能够取到的数字之和的最大值。

这个问题的经典解法是使用动态规划，时间复杂度为O(N²)。但题目还有一个进阶版本：如果允许两个人同时从起点出发，各自独立移动（两人路径可以交叉但不能重复取同一个格子的数字），问两人能够取到的数字之和的最大值是多少？这就是P1004这道题的核心所在。

2. 动态规划思路分析

2.1 单人问题的DP解法回顾

对于单人取数问题，我们可以定义dp[i][j]表示从(1,1)走到(i,j)时能获得的最大和。状态转移方程为： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

这个方程表示当前格子的最大值来自上方或左方的较大值加上当前格子的数值。

2.2 双人问题的扩展思路

当问题扩展到两个人时，我们需要考虑两人的路径可能会交叉的情况。这时候简单的二维DP就不够用了，需要升维处理。

我们可以定义dp[i1][j1][i2][j2]表示第一个人走到(i1,j1)，第二个人走到(i2,j2)时的最大和。但这样会有O(N⁴)的空间复杂度，对于N=9的题目来说虽然可行，但不够优雅。

更聪明的做法是注意到两人的步数是同步的（因为每次只能移动一步），所以可以用步数k作为一维，即dp[k][i1][i2]表示两人都走了k步，第一个人在i1行，第二个人在i2行时的最大和。因为k=i1+j1-1=i2+j2-1，所以j1和j2可以通过k和i1、i2计算得出。

3. 具体实现细节

3.1 状态转移方程

定义dp[k][i1][i2]为两人都走了k步，第一个人在i1行，第二个人在i2行时的最大和。那么状态转移需要考虑四种情况：

1. 两人都从上方移动下来
2. 第一人从上方，第二人从左方
3. 第一人从左方，第二人从上方
4. 两人都从左方移动过来

状态转移方程为： dp[k][i1][i2] = max( dp[k-1][i1-1][i2-1], dp[k-1][i1-1][i2], dp[k-1][i1][i2-1], dp[k-1][i1][i2] ) + (i1 == i2 ? grid[i1][k+1-i1] : grid[i1][k+1-i1] + grid[i2][k+1-i2])

3.2 边界条件处理

• 初始状态：dp[0][1][1] = grid[1][1]（两人都在起点）
• 当i1或i2超出网格范围时，对应的状态无效
• 当j1或j2超出网格范围时，对应的状态也无效

3.3 空间优化技巧

由于dp[k]只依赖于dp[k-1]，所以可以使用滚动数组技术将空间复杂度从O(N³)优化到O(N²)，只需要保存当前步和前一步的状态即可。

4. 代码实现示例

#include <iostream> #include <algorithm> using namespace std; const int N = 10; int grid[N][N]; int dp[2*N][N][N]; int main() { int n; cin >> n; int x, y, v; while (cin >> x >> y >> v, x || y || v) { grid[x][y] = v; } for (int k = 2; k <= 2*n; k++) { for (int i1 = 1; i1 <= n; i1++) { for (int i2 = 1; i2 <= n; i2++) { int j1 = k - i1, j2 = k - i2; if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue; int &curr = dp[k][i1][i2]; curr = max(curr, dp[k-1][i1-1][i2-1]); curr = max(curr, dp[k-1][i1-1][i2]); curr = max(curr, dp[k-1][i1][i2-1]); curr = max(curr, dp[k-1][i1][i2]); if (i1 == i2) { curr += grid[i1][j1]; } else { curr += grid[i1][j1] + grid[i2][j2]; } } } } cout << dp[2*n][n][n] << endl; return 0; }

5. 算法优化与变种

5.1 时间复杂度分析

原始算法的时间复杂度是O(N³)，因为有三层循环：

• 外层k循环：2N次
• 中层i1循环：N次
• 内层i2循环：N次

对于NOIP竞赛中的N=9来说，这个复杂度完全可接受。

5.2 空间优化实现

使用滚动数组优化空间：

int dp[2][N][N]; int now = 0, prev = 1; for (int k = 2; k <= 2*n; k++) { swap(now, prev); for (int i1 = 1; i1 <= n; i1++) { for (int i2 = 1; i2 <= n; i2++) { // 同上状态转移 } } }

5.3 问题变种思考

1. 如果允许更多路径（如三个人）怎么办？

   • 思路相同，继续增加DP维度即可，但复杂度会急剧上升

2. 如果网格很大（如N=100）怎么办？

   • 需要考虑更高效的算法或近似算法

3. 如果移动方向增加（如允许斜向移动）怎么办？

   • 状态转移需要考虑更多情况

6. 竞赛技巧与注意事项

6.1 调试技巧

1. 对于小规模数据（如N=2或3），可以手工计算验证程序正确性
2. 打印中间状态，特别是边界情况
3. 注意数组下标是否越界

6.2 常见错误

1. 忘记处理两人走到同一格时数字只能取一次的情况
2. 边界条件处理不当，如k=1时的特殊情况
3. 数组初始化不充分，导致初始状态错误

6.3 竞赛策略

1. 先解决单人问题，确保基础DP正确
2. 再扩展到双人情况，逐步增加复杂度
3. 对于部分分，可以考虑较简单的解法（如记忆化搜索）

7. 实际应用与扩展

虽然这个问题看起来是纯理论性的，但它实际上有许多实际应用场景：

1. 资源分配问题：如两个工人同时从不同路径收集资源
2. 网络流量优化：两条数据路径的最优传输
3. 物流路径规划：两辆运输车的最优配送路线

这类问题的核心思想——多维动态规划，在解决复杂优化问题时非常有用。掌握这个技巧可以帮助我们更好地处理现实世界中的各种路径优化和资源分配问题。