动态规划解最小路径和问题：LeetCode 64题详解-平芜编程栈

1. 最小路径和问题解析

这道题目来自著名的LeetCode Hot 100系列，编号64。给定一个m×n的非负整数网格，我们需要找到从左上角到右下角的路径，使得路径上的数字总和最小。每次移动只能向下或者向右一步。

这个问题看似简单，但蕴含着动态规划的经典思想。在实际应用中，类似的场景非常常见，比如物流路径规划、游戏地图寻路、资源分配优化等。理解这个问题的解法，能帮助我们掌握动态规划的核心思维方式。

2. 动态规划解法详解

2.1 状态定义与转移方程

我们定义dp[i][j]表示从起点(0,0)到位置(i,j)的最小路径和。根据题目限制，每个位置只能从上方或左方到达，因此状态转移方程为：

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

这个方程的意思是：到达当前位置的最小路径和，等于上方或左方较小值加上当前位置的值。

2.2 边界条件处理

对于第一行和第一列的特殊情况需要单独处理：

第一行的每个位置只能从左方到达
第一列的每个位置只能从上方到达

因此边界条件为：

dp[0][0] = grid[0][0]
第一行：dp[0][j] = dp[0][j-1] + grid[0][j]
第一列：dp[i][0] = dp[i-1][0] + grid[i][0]

2.3 代码实现示例

def minPathSum(grid): m, n = len(grid), len(grid[0]) dp = [[0]*n for _ in range(m)] dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 填充剩余表格 for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[-1][-1]

3. 空间复杂度优化

3.1 滚动数组优化

观察状态转移方程，我们发现dp[i][j]只依赖于上一行和当前行的数据。因此可以将空间复杂度从O(mn)优化到O(n)：

def minPathSum(grid): m, n = len(grid), len(grid[0]) dp = [0]*n dp[0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] # 处理剩余行 for i in range(1, m): dp[0] += grid[i][0] # 更新第一列 for j in range(1, n): dp[j] = min(dp[j], dp[j-1]) + grid[i][j] return dp[-1]

3.2 原地修改优化

如果允许修改原数组，我们可以直接在原数组上进行计算，将空间复杂度优化到O(1)：

def minPathSum(grid): m, n = len(grid), len(grid[0]) # 初始化第一行 for j in range(1, n): grid[0][j] += grid[0][j-1] # 初始化第一列 for i in range(1, m): grid[i][0] += grid[i-1][0] # 填充剩余表格 for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[-1][-1]

4. 算法复杂度分析

时间复杂度：O(mn)，因为我们需要遍历整个网格一次
空间复杂度：
- 基础版本：O(mn)
- 滚动数组优化：O(n)
- 原地修改：O(1)

5. 实际应用场景

最小路径和问题在实际中有广泛的应用：

物流路径规划：计算从仓库到目的地的最小运输成本路径
游戏开发：寻找角色移动的最小消耗路径
资源分配：优化资源使用路径，最小化总成本
图像处理：寻找图像中最小能量路径进行接缝裁剪

6. 常见问题与调试技巧

6.1 边界条件错误

常见错误是忘记处理第一行和第一列的特殊情况。调试时：

检查网格大小为1×1的情况
检查只有一行或一列的情况

6.2 初始化错误

确保dp数组初始值正确：

dp[0][0]必须等于grid[0][0]
第一行和第一列的初始化要连续累加

6.3 空间优化时的覆盖问题

使用滚动数组优化时，注意不要覆盖还需要使用的数据。建议：

先更新当前行的第一列
然后从左到右更新其他列

7. 算法扩展与变种

7.1 允许对角线移动

如果允许从左上、左、上三个方向移动，只需修改状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + grid[i][j]

7.2 带障碍物的网格

类似LeetCode 63题，某些格子不可达：

遇到障碍物时dp值设为无穷大
转移时跳过障碍物格子

7.3 输出具体路径

如果需要输出具体路径而不仅仅是和：

额外维护一个path数组记录选择
回溯时根据dp值决定移动方向

8. 性能优化建议

对于特别大的网格：

优先使用空间优化版本
考虑并行计算：每行可以独立计算
如果网格有特殊结构（如稀疏），可以针对性优化

9. 测试用例设计

全面的测试用例应包括：

1×1网格
单行或单列网格
常规矩形网格
包含0值的网格
所有值相同的网格
随机生成的大型网格

示例测试用例：

def test_minPathSum(): assert minPathSum([[1]]) == 1 assert minPathSum([[1,3,1],[1,5,1],[4,2,1]]) == 7 assert minPathSum([[1,2,3],[4,5,6]]) == 12 assert minPathSum([[0,0,0],[0,0,0]]) == 0