1. 问题背景与题目解析洛谷P2196是一道经典的动态规划题目源自1996年全国青少年信息学奥林匹克竞赛NOIP提高组。题目描述了一个地下有若干地雷的房间每个房间标有地雷数量玩家从入口出发每次只能向右或向下移动需要找到一条路径使得经过的房间地雷总数最大。这道题目在算法竞赛中具有标志性意义它不仅是动态规划入门的经典案例也很好地体现了最优子结构和无后效性这两个动态规划的核心特征。题目看似简单但能考察选手对状态转移方程的构建能力。2. 动态规划解法详解2.1 状态定义我们定义一个二维数组dp[i][j]表示从起点(1,1)走到位置(i,j)时能够获得的最大地雷数。这个状态定义是解决此类网格路径问题的常见方法。例如对于如下地雷分布1 2 3 4 5 6 7 8 9dp[2][2]就表示从(1,1)走到(2,2)即数字5的位置能获得的最大地雷数。2.2 状态转移方程根据题目规则只能向右或向下移动每个位置(i,j)的最大值只能来自其上方(i-1,j)或左方(i,j-1)。因此状态转移方程为dp[i][j] max(dp[i-1][j], dp[i][j-1]) mine[i][j]其中mine[i][j]表示位置(i,j)的地雷数量。边界情况处理第一行(i1)的点只能从左方来第一列(j1)的点只能从上方来起点dp[1][1] mine[1][1]2.3 实现步骤初始化dp数组大小与地雷矩阵相同dp[1][1] mine[1][1]填充第一行dp[1][j] dp[1][j-1] mine[1][j]填充第一列dp[i][1] dp[i-1][1] mine[i][1]按行或列顺序填充其余位置使用状态转移方程dp[n][m]即为最终结果3. 代码实现与优化3.1 基础实现C#include iostream #include algorithm using namespace std; int main() { int n, m; cin n m; int mine[n1][m1], dp[n1][m1]; // 输入地雷矩阵 for(int i1; in; i) for(int j1; jm; j) cin mine[i][j]; // 初始化dp数组 dp[1][1] mine[1][1]; // 填充第一行和第一列 for(int j2; jm; j) dp[1][j] dp[1][j-1] mine[1][j]; for(int i2; in; i) dp[i][1] dp[i-1][1] mine[i][1]; // 填充其余位置 for(int i2; in; i) for(int j2; jm; j) dp[i][j] max(dp[i-1][j], dp[i][j-1]) mine[i][j]; cout dp[n][m] endl; return 0; }3.2 空间优化注意到dp[i][j]只依赖于当前行和前一行可以将空间复杂度从O(nm)优化到O(m)int dp[2][m1]; // 只保留两行 int now 0, prev 1; dp[now][1] mine[1][1]; for(int j2; jm; j) dp[now][j] dp[now][j-1] mine[1][j]; for(int i2; in; i) { swap(now, prev); // 交换当前行和前一行 dp[now][1] dp[prev][1] mine[i][1]; for(int j2; jm; j) dp[now][j] max(dp[prev][j], dp[now][j-1]) mine[i][j]; }4. 路径记录与输出4.1 记录路径的方法为了不仅输出最大值还能输出具体路径我们需要额外维护一个path数组记录每个点的来源// 0表示来自上方1表示来自左方 int path[n1][m1]; // 在填充dp数组时记录路径 if(dp[i-1][j] dp[i][j-1]) { dp[i][j] dp[i-1][j] mine[i][j]; path[i][j] 0; // 来自上方 } else { dp[i][j] dp[i][j-1] mine[i][j]; path[i][j] 1; // 来自左方 }4.2 回溯输出路径从终点(n,m)开始回溯到起点(1,1)void printPath(int i, int j) { if(i 1 j 1) { cout ( i , j ); return; } if(path[i][j] 0) printPath(i-1, j); else printPath(i, j-1); cout - ( i , j ); }5. 常见错误与调试技巧5.1 数组越界问题确保数组下标从1开始使用时声明大小要1边界条件i1或j1要单独处理多测时要记得清空数组5.2 初始化错误dp[1][1]必须初始化为mine[1][1]第一行和第一列的初始化要单独处理5.3 状态转移错误确保比较的是dp[i-1][j]和dp[i][j-1]不要写反记得加上当前点的地雷数mine[i][j]5.4 调试建议对于小样例如2x2矩阵手动计算dp值验证打印中间dp数组检查填充过程使用assert检查边界条件6. 算法复杂度分析时间复杂度O(nm)因为需要填充n×m的dp表格空间复杂度基础版本O(nm)优化版本O(m)路径记录会增加O(nm)的空间但不影响时间复杂度7. 类似题目与扩展7.1 类似题目推荐洛谷P1002 [过河卒]棋盘路径计数问题洛谷P1216 [数字三角形]三角形路径最大和LeetCode 64. Minimum Path Sum最小路径和问题7.2 题目变种思考如果允许斜向移动向右下如何修改状态转移方程如果某些格子是障碍物不能通过如何修改算法如果需要找出前k优的路径该如何解决8. 竞赛中的应用技巧在实际竞赛中处理此类题目时先画小样例的dp表格确保理解状态转移注意输入输出的格式要求考虑是否需要进行空间优化根据数据范围如果时间允许可以写一个暴力搜索程序对拍注意题目是否要求输出路径提前规划好代码结构这道题目虽然简单但它体现了动态规划的核心思想。我在多次比赛中发现很多复杂的动态规划问题都可以看作是这个基础模型的扩展。掌握这类网格路径问题的解法对解决更复杂的动态规划问题大有裨益。
