韩国风格网站整站源码,站内免费推广,网页设计公司理念,百度地图网站开发在解 LeetCode 的过程中#xff0c;路径计数问题是动态规划中一个经典的例子。今天我来分享一道非常基础但极具代表性的题目——不同路径。不仅适合初学者入门 DP#xff08;动态规划#xff09;#xff0c;还能帮助你打下递归思维的基础。
本文将介绍#xff1a;
…在解 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 步向右。总共 mn-2 步从中选择 m-1 步向下。
公式
C(mn−2,m−1)(mn−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 动态规划题解敬请期待
