动态规划入门：NOIP经典地雷路径问题解析

发布时间：2026/10/29 8:26:45
动态规划入门：NOIP经典地雷路径问题解析

1. 问题背景与题目解析

洛谷P2196是一道经典的动态规划题目，源自1996年全国青少年信息学奥林匹克竞赛（NOIP）提高组。题目描述了一个地下有若干地雷的房间，每个房间标有地雷数量，玩家从入口出发，每次只能向右或向下移动，需要找到一条路径使得经过的房间地雷总数最大。

这道题目在算法竞赛中具有标志性意义，它不仅是动态规划入门的经典案例，也很好地体现了"最优子结构"和"无后效性"这两个动态规划的核心特征。题目看似简单，但能考察选手对状态转移方程的构建能力。

2. 动态规划解法详解

2.1 状态定义

我们定义一个二维数组dp[i][j]，表示从起点(1,1)走到位置(i,j)时能够获得的最大地雷数。这个状态定义是解决此类网格路径问题的常见方法。

例如，对于如下地雷分布：

1 2 3 4 5 6 7 8 9

dp[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)的地雷数量。

边界情况处理：

  • 第一行(i=1)的点只能从左方来
  • 第一列(j=1)的点只能从上方来
  • 起点dp[1][1] = mine[1][1]

2.3 实现步骤

  1. 初始化dp数组，大小与地雷矩阵相同
  2. dp[1][1] = mine[1][1]
  3. 填充第一行：dp[1][j] = dp[1][j-1] + mine[1][j]
  4. 填充第一列：dp[i][1] = dp[i-1][1] + mine[i][1]
  5. 按行或列顺序填充其余位置，使用状态转移方程
  6. dp[n][m]即为最终结果

3. 代码实现与优化

3.1 基础实现（C++）

#include <iostream> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; int mine[n+1][m+1], dp[n+1][m+1]; // 输入地雷矩阵 for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> mine[i][j]; // 初始化dp数组 dp[1][1] = mine[1][1]; // 填充第一行和第一列 for(int j=2; j<=m; j++) dp[1][j] = dp[1][j-1] + mine[1][j]; for(int i=2; i<=n; i++) dp[i][1] = dp[i-1][1] + mine[i][1]; // 填充其余位置 for(int i=2; i<=n; i++) for(int j=2; j<=m; 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][m+1]; // 只保留两行 int now = 0, prev = 1; dp[now][1] = mine[1][1]; for(int j=2; j<=m; j++) dp[now][j] = dp[now][j-1] + mine[1][j]; for(int i=2; i<=n; i++) { swap(now, prev); // 交换当前行和前一行 dp[now][1] = dp[prev][1] + mine[i][1]; for(int j=2; j<=m; j++) dp[now][j] = max(dp[prev][j], dp[now][j-1]) + mine[i][j]; }

4. 路径记录与输出

4.1 记录路径的方法

为了不仅输出最大值，还能输出具体路径，我们需要额外维护一个path数组记录每个点的来源：

// 0表示来自上方，1表示来自左方 int path[n+1][m+1]; // 在填充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
  • 边界条件（i=1或j=1）要单独处理
  • 多测时要记得清空数组

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 类似题目推荐

  1. 洛谷P1002 [过河卒]：棋盘路径计数问题
  2. 洛谷P1216 [数字三角形]：三角形路径最大和
  3. LeetCode 64. Minimum Path Sum：最小路径和问题

7.2 题目变种思考

  • 如果允许斜向移动（向右下），如何修改状态转移方程？
  • 如果某些格子是障碍物不能通过，如何修改算法？
  • 如果需要找出前k优的路径，该如何解决？

8. 竞赛中的应用技巧

在实际竞赛中处理此类题目时：

  1. 先画小样例的dp表格，确保理解状态转移
  2. 注意输入输出的格式要求
  3. 考虑是否需要进行空间优化（根据数据范围）
  4. 如果时间允许，可以写一个暴力搜索程序对拍
  5. 注意题目是否要求输出路径，提前规划好代码结构

这道题目虽然简单，但它体现了动态规划的核心思想。我在多次比赛中发现，很多复杂的动态规划问题都可以看作是这个基础模型的扩展。掌握这类网格路径问题的解法，对解决更复杂的动态规划问题大有裨益。