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

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⁴)的空间复杂度对于N9的题目来说虽然可行但不够优雅。更聪明的做法是注意到两人的步数是同步的因为每次只能移动一步所以可以用步数k作为一维即dp[k][i1][i2]表示两人都走了k步第一个人在i1行第二个人在i2行时的最大和。因为ki1j1-1i2j2-1所以j1和j2可以通过k和i1、i2计算得出。3. 具体实现细节3.1 状态转移方程定义dp[k][i1][i2]为两人都走了k步第一个人在i1行第二个人在i2行时的最大和。那么状态转移需要考虑四种情况两人都从上方移动下来第一人从上方第二人从左方第一人从左方第二人从上方两人都从左方移动过来状态转移方程为 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][k1-i1] : grid[i1][k1-i1] grid[i2][k1-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竞赛中的N9来说这个复杂度完全可接受。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 问题变种思考如果允许更多路径如三个人怎么办思路相同继续增加DP维度即可但复杂度会急剧上升如果网格很大如N100怎么办需要考虑更高效的算法或近似算法如果移动方向增加如允许斜向移动怎么办状态转移需要考虑更多情况6. 竞赛技巧与注意事项6.1 调试技巧对于小规模数据如N2或3可以手工计算验证程序正确性打印中间状态特别是边界情况注意数组下标是否越界6.2 常见错误忘记处理两人走到同一格时数字只能取一次的情况边界条件处理不当如k1时的特殊情况数组初始化不充分导致初始状态错误6.3 竞赛策略先解决单人问题确保基础DP正确再扩展到双人情况逐步增加复杂度对于部分分可以考虑较简单的解法如记忆化搜索7. 实际应用与扩展虽然这个问题看起来是纯理论性的但它实际上有许多实际应用场景资源分配问题如两个工人同时从不同路径收集资源网络流量优化两条数据路径的最优传输物流路径规划两辆运输车的最优配送路线这类问题的核心思想——多维动态规划在解决复杂优化问题时非常有用。掌握这个技巧可以帮助我们更好地处理现实世界中的各种路径优化和资源分配问题。