1. 问题背景与定义
"不同路径"是一个经典的动态规划问题，通常出现在算法学习和编程面试中。问题描述如下：在一个m×n的网格中，机器人位于左上角（起点），每次只能向右或向下移动一步，问到达右下角（终点）共有多少条不同的路径。
这个问题看似简单，却蕴含着丰富的数学原理和算法思想。它不仅考察对组合数学的理解，更是动态规划入门的最佳案例之一。在实际应用中，类似场景广泛存在于物流路径规划、机器人导航、游戏AI寻路等领域。
2. 组合数学解法
2.1 排列组合原理
从起点到终点，机器人需要恰好移动(m-1)次向下和(n-1)次向右。因此，不同路径的总数等于从(m+n-2)步中选择(m-1)步向下（或(n-1)步向右）的组合数。
计算公式为： C(m+n-2, m-1) = (m+n-2)! / [(m-1)! × (n-1)!]
2.2 实现注意事项
直接计算阶乘容易导致整数溢出。更稳健的实现方式是：
def uniquePaths(m, n): total = m + n - 2 k = min(m, n) - 1 res = 1 for i in range(1, k+1): res = res * (total - k + i) // i return res注意：使用整数除法(//)而非浮点除法(/)以避免精度问题。Python中的//可以保证结果为整数。
3. 动态规划解法
3.1 状态定义与转移方程
设dp[i][j]表示到达(i,j)格子的路径数，则有：
- 初始条件：dp[0][j] = dp[i][0] = 1（第一行和第一列只有一种走法）
- 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]（来自上方或左方的路径之和）
3.2 空间优化技巧
实际实现时不需要维护完整的二维数组。观察到每个格子只依赖左边和上边的值，可以用滚动数组优化空间：
def uniquePaths(m, n): dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[-1]4. 障碍物变种问题
4.1 问题扩展
当网格中存在障碍物时（标记为1），需要跳过这些不可达的格子。转移方程变为：
if obstacleGrid[i][j] == 1: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1]4.2 边界处理技巧
在处理第一行和第一列时，一旦遇到障碍物，后续所有格子都不可达：
# 初始化第一列 for i in range(m): if obstacleGrid[i][0] == 1: for k in range(i, m): dp[k][0] = 0 break dp[i][0] = 15. 性能对比与选择建议
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 组合数学 | O(min(m,n)) | O(1) | 无障碍物标准网格 |
| 基础动态规划 | O(mn) | O(mn) | 通用性强，易扩展 |
| 优化动态规划 | O(mn) | O(n) | 空间敏感的标准网格问题 |
建议优先选择组合数学解法（无障碍物时），其次考虑空间优化后的动态规划。当需要处理障碍物等复杂情况时，标准动态规划更具扩展性。
6. 常见错误与调试技巧
- 数组越界：确保正确处理m=1或n=1的边界情况
- 整数溢出：组合数计算时使用累乘累除法而非直接计算阶乘
- 障碍物处理：注意初始化时第一行/列遇到障碍物后的处理
- 方向混淆：明确矩阵的行列对应关系（通常m行n列）
调试时可以打印中间dp表：
for row in dp: print(row)7. 实际应用案例
- 物流仓储：AGV小车在货架间的路径规划
- 游戏开发：战略游戏中单位移动范围计算
- 电路设计：布线时避开障碍区域的方案计数
- 生物信息学：蛋白质折叠路径分析
在解决实际问题时，往往需要结合业务场景进行扩展。比如在物流系统中，不同路径可能有不同的成本，这时就需要引入加权路径的变种问题。
