[特殊字符] LeetCode 62. 不同路径 | 动态规划+递归优化详解
在解 LeetCode 的过程中，路径计数问题是动态规划中一个经典的例子。今天我来分享一道非常基础但极具代表性的题目——不同路径。不仅适合初学者入门 DP（动态规划），还能帮助你打下递归思维的基础。
本文将介绍：
- 🔍 问题描述
- 💡 解题思路（包括递归+记忆化搜索）
- 🏆 代码实现与优化
- 📊 时间复杂度 & 空间复杂度分析
- 🔥 进阶思考
🔍 问题描述
一个机器人位于一个 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 动态规划题解，敬请期待！