[特殊字符] LeetCode 62. 不同路径 | 动态规划+递归优化详解

在解 LeetCode 的过程中，路径计数问题是动态规划中一个经典的例子。今天我来分享一道非常基础但极具代表性的题目——不同路径。不仅适合初学者入门 DP（动态规划），还能帮助你打下递归思维的基础。

本文将介绍：

1. 🔍 问题描述
2. 💡 解题思路（包括递归+记忆化搜索）
3. 🏆 代码实现与优化
4. 📊 时间复杂度 & 空间复杂度分析
5. 🔥 进阶思考

---

🔍 问题描述

一个机器人位于一个 m x n 的网格左上角（起点 Start）。

机器人每次只能向 右 或 下 移动一步，试图到达网格的右下角（终点 Finish）。

请问从起点到终点总共有多少条不同的路径？

✅ 示例

示例 1：

输入: m = 3, n = 7
输出: 28

示例 2：

输入: m = 3, n = 2
输出: 3
解释: 
1. 向右 -> 向下 -> 向下  
2. 向下 -> 向下 -> 向右  
3. 向下 -> 向右 -> 向下

示例 3：

输入: m = 7, n = 3
输出: 28

示例 4：

输入: m = 3, n = 3
输出: 6

---

💡 解题思路

1️⃣ 递归 + 记忆化搜索（自顶向下）

我们可以把每一步的选择抽象成一个状态转移问题：

• 如果机器人在 (i, j) 位置，它可以从 上面 (i-1, j) 或 左边 (i, j-1) 走过来。
• 到达 (i, j) 的总路径数等于从 (i-1, j) 和 (i, j-1) 走过来的路径数之和。

状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件：

• 第一行和第一列上的每个位置的路径数都是 1（因为只能往一个方向走）。

为什么需要记忆化？
如果不加记忆化，递归会重复计算相同子问题，时间复杂度会指数级上升。通过记忆化存储已经计算过的结果，避免重复计算，大大降低了复杂度。

---

🏆 代码实现（Java）

class Solution {public int uniquePaths(int m, int n) {// 创建一个记忆数组，存储子问题的解int[][] memo = new int[m][n];return dfs(m - 1, n - 1, memo);}// 递归搜索函数，i 表示行数，j 表示列数private int dfs(int i, int j, int[][] memo) {// 边界情况，越界直接返回 0if (i < 0 || j < 0) {return 0;}// 如果到达起点 (0,0)，只有 1 条路径if (i == 0 && j == 0) {return 1;}// 如果该位置已经计算过，直接返回记忆值if (memo[i][j] != 0) {return memo[i][j];}// 从上面和左边的路径数之和return memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);}
}

---

📊 时间复杂度 & 空间复杂度分析

• 时间复杂度： O(m * n)
  每个位置只会被访问一次，避免了重复计算。

• 空间复杂度： O(m * n)
  使用了一个二维数组来保存子问题的解。

---

🔥 进阶思考：动态规划（自底向上）

除了递归+记忆化，还可以使用**动态规划（DP）**的方式自底向上求解，避免了递归的栈消耗。

代码实现（DP）：

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;// 状态转移方程填表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];}
}

时间复杂度: O(m * n)
空间复杂度: O(m * n)（可以优化到 O(n)，只用一维数组）

---

📚 其他进阶解法（组合数学）

如果你喜欢数学，可以用组合数的公式来解这道题：

• 一共需要移动 m-1 步向下，n-1 步向右。
• 总共 m+n-2 步，从中选择 m-1 步向下。

公式：

C(m+n−2,m−1)=(m+n−2)!(m−1)!⋅(n−1)!C(m + n - 2, m - 1) = \frac{(m + n - 2)!}{(m - 1)! \cdot (n - 1)!}

Java 实现：

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

时间复杂度: O(min(m, n))
空间复杂度: O(1)

---

🎯 总结

• 🚀 使用 递归+记忆化搜索 解决子问题，避免重复计算。
• 🏆 使用 动态规划 解决自底向上的问题，避免递归栈溢出。
• ✨ 组合数学 提供最优解法，时间复杂度低，适合大规模输入。

如果你觉得这篇文章对你有帮助，别忘了点赞👍、收藏⭐和关注👀！欢迎在评论区和我交流更多动态规划的问题！

---

📢 更多 LeetCode 动态规划题解，敬请期待！