动态规划解决网格路径问题：从基础到优化

1. 网格图路径问题的动态规划本质

网格图路径问题作为动态规划的经典应用场景，完美诠释了"最优子结构"和"重叠子问题"两大核心特征。想象你站在一个m×n网格的起点，每次只能向右或向下移动，目标是到达右下角终点。这个问题看似简单，却蕴含着动态规划最精妙的思想内核。

从算法设计的角度看，每个网格点的路径总数实际上等于其上方点和左侧点路径数之和。这种递推关系可以用状态转移方程表示为：

python复制dp[i][j] = dp[i-1][j] + dp[i][j-1]

其中边界条件为第一行和第一列的所有点路径数均为1（因为只有单一方向的移动方式）。这个简单的例子揭示了动态规划解决网格问题的通用范式：

1. 定义状态表示（这里dp[i][j]表示到达(i,j)的路径数）
2. 建立状态转移方程
3. 确定边界条件
4. 选择计算顺序（通常从左到右、从上到下填充）

关键提示：在实际编码时，我们经常会遇到网格中存在障碍物的情况。这时只需在状态转移时增加条件判断——如果当前格子是障碍物，则直接置为0（表示不可达）。

2. 基础模型与变种问题全解析

2.1 经典网格路径问题

最基本的网格路径问题要求计算从左上角到右下角的路径总数。这个问题可以通过组合数学直接求解（需要移动m-1次下和n-1次右，总路径数为C(m+n-2, m-1)），但动态规划的方法更具通用性，可以轻松扩展到更复杂的场景。

实现代码示例：

python复制def uniquePaths(m, n):
    dp = [[1]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]

2.2 带障碍物的网格路径

当网格中存在障碍物时，问题复杂度提升。这时需要：

1. 初始化时处理第一行和第一列（遇到障碍物后所有后续格子都不可达）
2. 状态转移时跳过障碍物格子

代码实现关键点：

python复制if obstacleGrid[i][j] == 1:
    dp[i][j] = 0
else:
    d