动态规划实战：二维网格最大金币收集问题解析-育师

1. 题目背景与核心考察点

这道题目源自信息学奥赛经典题库，同时在洛谷平台以题号P14078收录，属于GESP七级认证考试中的典型动态规划问题。题目描述了一个二维网格地图，每个格子存放不同数量的金币，玩家从左上角出发，每次只能向右或向下移动，最终到达右下角时需要收集尽可能多的金币。

这类题型在算法竞赛中被称为"数字三角形"问题的二维扩展版本，其核心考察的是动态规划中的"无后效性"和"最优子结构"特性。通过这个题目，可以深入理解以下关键概念：

状态定义：dp[i][j]表示到达(i,j)位置时能获得的最大金币数
状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + gold[i][j]
边界处理：第一行和第一列的特殊情况

2. 动态规划解法详解

2.1 基础状态转移实现

最直观的解法是使用二维数组存储中间状态。以下是C++实现的关键代码片段：

int collectGold(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); dp[0][0] = grid[0][0]; // 初始化第一列 for(int i = 1; i < m; ++i) dp[i][0] = dp[i-1][0] + grid[i][0]; // 初始化第一行 for(int j = 1; j < n; ++j) dp[0][j] = dp[0][j-1] + grid[0][j]; // 状态转移 for(int i = 1; i < m; ++i) for(int j = 1; j < n; ++j) dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]; return dp[m-1][n-1]; }

注意：在实际竞赛中，建议将dp数组声明为全局变量以避免栈溢出，特别是当网格尺寸较大时（如n,m > 1000）

2.2 空间优化技巧

观察到每个状态只依赖于上方和左方的状态，可以将空间复杂度从O(mn)优化到O(n)：

int collectGoldOpt(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<int> dp(n, 0); dp[0] = grid[0][0]; // 初始化第一行 for(int j = 1; j < n; ++j) dp[j] = dp[j-1] + grid[0][j]; // 逐行处理 for(int i = 1; i < m; ++i) { dp[0] += grid[i][0]; // 每行第一个元素 for(int j = 1; j < n; ++j) dp[j] = max(dp[j], dp[j-1]) + grid[i][j]; } return dp[n-1]; }

这种优化在m远大于n时效果显著，比如处理10000×100的网格，内存消耗仅为原来的1/100。

3. 算法正确性证明

3.1 最优子结构性质

对于任意非边界点(i,j)，到达该点的最优路径必定经过(i-1,j)或(i,j-1)。假设存在一条更优路径不满足此性质，则会导致矛盾，因为任何到达(i,j)的路径都必须经过其上方或左方的点。

3.2 无后效性验证

某个阶段的状态一旦确定，后续决策不受之前决策的影响。在本问题中，dp[i][j]的值仅由grid[i][j]和之前计算好的dp[i-1][j]、dp[i][j-1]决定，完全符合无后效性要求。

4. 变种与扩展

4.1 允许对角线移动

若题目改为允许从左上、正上、左方三个方向移动，只需修改状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + grid[i][j];

4.2 收集路径重建

需要输出具体收集路径时，可以额外维护一个path数组记录决策来源：

vector<vector<char>> path(m, vector<char>(n, ' ')); // 在状态转移时记录决策 if(dp[i-1][j] > dp[i][j-1]) { dp[i][j] = dp[i-1][j] + grid[i][j]; path[i][j] = 'D'; // 来自上方(Down) } else { dp[i][j] = dp[i][j-1] + grid[i][j]; path[i][j] = 'R'; // 来自右方(Right) }

回溯路径时从终点逆向追踪即可。