动态规划解决二维网格最小路径和问题

1. 问题定义与场景分析

在算法竞赛和编程面试中，二维网格最小路径和问题是一个高频出现的经典动态规划题目。题目通常描述为：给定一个包含非负整数的 m x n 网格，每次只能向下或者向右移动一步，找到从左上角到右下角的路径，使得路径上的数字总和为最小。

这个问题的实际应用场景非常广泛：

• 机器人路径规划中的能耗最小化
• 物流配送中的最短成本路线计算
• 游戏开发中的AI移动决策
• 金融领域中的最优投资路径选择

以物流配送为例，假设网格中的每个数字代表通过该区域的时间成本，我们需要找到从仓库（左上角）到客户地址（右下角）耗时最少的配送路线。这个问题看似简单，但蕴含着动态规划的核心思想。

2. 动态规划基础与解题思路

2.1 为什么选择动态规划

动态规划特别适合解决具有以下特征的问题：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：在递归求解过程中会重复计算相同的子问题
3. 无后效性：当前状态一旦确定，后续决策不受之前决策影响

在最小路径和问题中：

• 到达(i,j)的最小路径和 = min(到达(i-1,j)的最小和，到达(i,j-1)的最小和) + grid[i][j]
• 在递归求解中会重复计算相同的网格点
• 当前点的最小和只取决于上方和左方的点，与如何到达它们无关

2.2 状态定义与转移方程

我们定义dp[i][j]表示从(0,0)到达(i,j)的最小路径和。状态转移方程可以表示为：

code复制dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

边界条件处理：

• 第一行(i=0)：只能从左方过来 dp[0][j] = dp[0][j-1] + grid[0][j]
• 第一列(j=0)：只能从上方过来 dp[i][0] = dp[i-1][0] + grid[i][0]
• 起点(0,0)：dp[0][0] = grid[0][0]

2.3 空间复杂度优化思路

原始方法需要O(mn)空间存储整个dp表。观察发现，计算dp[i][j]时只需要上一行和当前行左侧的数据，因此可以优化为：

1. 单行滚动数组：O(n)空间
2. 原地修改：直接利用原始grid数组（如果允许修改输入）

3. C++实现与详细解析

3.1 基础版本实现

cpp复制int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    if (m == 0) return 0;
    int n = grid[0].size();
    
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    
    // 初始化第一行
    for (int j = 1; j < n; ++j