题目简介

在一个 m x n 的网格中，机器人从左上角出发，每次只能向下或向右移动一步，最终到达右下角。问总共有多少条不同的路径？这道题是动态规划领域的经典入门题，也是理解「状态转移」思想的绝佳案例。

从示例中可以直观看到：当 m=3, n=7 时，输出为 28；当 m=3, n=3 时，输出为 6。这背后隐藏着怎样的数学规律？让我们通过动态规划的方法逐步揭开谜底。

解题思路

动态规划三要素

1. 状态定义
   ：设 dp[i][j] 为到达 (i,j) 位置的路径总数
2. 转移方程
   ：dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上方或左方到达当前位置）
3. 边界条件
   ：第一行和第一列的所有位置都只有 1 条路径（只能一直向右或一直向下）

流程图清晰展示了计算过程：从左上角开始，先初始化第一行和第一列，再按行优先顺序填充整个表格。以 3x3 网格为例，dp[2][2] 的值由 dp[1][2] 和 dp[2][1] 相加得到，最终推导出右下角的结果。

代码实现

class Solution {    public int uniquePaths(int m, int n) {        int[][] dp = new int[m][n];        // 初始化第一列        for (int i = 0; i < m; i++) {            dp[i][0] = 1;        }        // 初始化第一行        for (int j = 0; j < n; j++) {            dp[0][j] = 1;        }        // 填充dp表        for (int i = 1; i < m; i++) {            for (int j = 1; j < n; j++) {                dp[i][j] = dp[i-1][j] + dp[i][j-1];            }        }        return dp[m-1][n-1];    }}



// 初始化第一行




代码解析

• 初始化阶段
  ：将第一行和第一列全部置为 1，因为这些位置只能通过一种方式到达
• 状态转移
  ：对于网格内部的每个位置 (i,j)，其路径数等于上方和左方路径数之和
• 时间复杂度
  ：O(m*n)，需要填充整个二维数组
• 空间复杂度
  ：O(m*n)，需要存储完整的 dp 表

复杂度分析

时间复杂度

• 基础实现
  ：O(m*n)，需要遍历整个网格
• 优化实现
  ：O(m*n)，时间复杂度不变，但常数项更小

空间复杂度

• 基础实现
  ：O(m*n)，需要二维数组存储所有状态
• 一维优化
  ：O(min(m,n))，只需存储一行或一列的状态
• 数学公式
  ：O(1)，直接计算组合数

从图表对比可以看出，三种方法在时间复杂度上相当，但空间优化效果显著。当网格规模较大（如 m,n=1000）时，空间优化能节省近百万的内存空间。

优化方案

1. 一维数组优化

public int uniquePaths(int m, int n) {    // 确保使用较小的维度作为数组长度    if (m > n) return uniquePaths(n, m);    int[] dp = new int[m];    Arrays.fill(dp, 1);    for (int j = 1; j < n; j++) {        for (int i = 1; i < m; i++) {            dp[i] += dp[i-1];        }    }    return dp[m-1];}

优化原理：当前行的状态只依赖于上一行和当前行的前一个状态，因此可以用一维数组滚动更新。

2. 数学公式法

从左上角到右下角共需移动 (m-1)+(n-1) = m+n-2 步，其中向下 m-1 步，向右 n-1 步。问题等价于在 m+n-2 步中选择 m-1 步向下走，即组合数 C(m+n-2, m-1)。


注意事项：计算组合数时需注意溢出问题，建议使用 long 类型中间变量，并采用逐步相乘再相除的方式避免溢出。

优化方案对比

public int uniquePaths(int m, int n) {    long result = 1;    for (int i = 1; i <= m-1; i++) {        result = result * (n-1 + i) / i;    }    return (int) result;}

类似题目推荐

1. LeetCode 63. 不同路径 II（中等）

特点：网格中存在障碍物，需要在状态转移时额外判断

关键差异：遇到障碍物时 dp[i][j] = 0

推荐指数：★★★★★

2. LeetCode 64. 最小路径和（中等）

特点：求从左上角到右下角的最小路径和

状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

推荐指数：★★★★☆

3. LeetCode 120. 三角形最小路径和（中等）

特点：三角形结构的网格，只能向下或向右下移动

空间优化：可优化至 O(n) 空间

推荐指数：★★★★☆

这些题目共同构成了动态规划的路径问题体系，从基础到进阶，逐步深入。掌握这些题目后，你将对「状态定义」和「转移方程」有更深刻的理解，为解决更复杂的动态规划问题打下坚实基础。

总结

LeetCode 62 题虽然简单，却蕴含了动态规划的核心思想。通过这道题，我们学习了：

1. 如何定义状态和推导转移方程
2. 多种空间优化技巧（一维数组、数学公式）
3. 组合数学在算法中的应用

动态规划的本质是「用空间换时间」，而优化的关键在于「减少不必要的空间存储」。当我们遇到新的动态规划问题时，不妨先尝试写出基础解法，再思考如何优化空间复杂度，这往往能带来意想不到的收获。

最后，建议通过推荐的类似题目进行巩固练习，特别是 63 题和 64 题，它们能帮助你更好地理解动态规划的变体应用。记住，算法学习的关键在于举一反三，触类旁通。动态规划在路径规划、资源分配、最优决策等领域有广泛应用，掌握这类问题的解题思路对解决实际工程问题具有重要价值。