☆打卡算法☆LeetCode 62、不同路径 算法解析
☆打卡算法☆LeetCode 62、不同路径 算法解析
恬静的小魔龙
发布于 2022-08-07 10:10:27
发布于 2022-08-07 10:10:27
一、题目
1、算法题目
“给定m * n带下的网格， 从网格左上角出发，求有多少条到右下角的路径。”
题目链接：
来源：力扣（LeetCode）
链接：62. 不同路径 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
image.png
示例 1：
输入： m = 3, n = 7
输出： 28示例 2：
输入：m = 3, n = 2
输出：3二、解题
1、思路分析
看到这种求出所有解的题，很容易就想到了动态规划。
这个首先要推算出来动态规划的方程，因为是从(0,0)触发，到(i,j)有dp[i][j]条路线。
求dp[i][j]，要思考移动的方式：
- 如果向下走，那么就是从dp[i-1,j]走过来
- 如果向右走，那么就会从dp[i,j-1]走过来
因此得到动态规划方程：
dp[i,j] = dp[i-1,j]+dp[i,j-1]
因为dp[i,j]只有这两个方向可以过来，然后初始化数组，从dp[0,0]开始，参考代码如下。
2、代码实现
代码参考：
public class Solution {
int[,] visited;
int[,] memo;
public int UniquePaths(int m, int n) {
visited = new int[m, n];
memo = new int[m, n];
return dfs(m, n, 0, 0);
}
public int dfs(int m, int n, int i, int j) {
if (i == m - 1 && j == n - 1) return 1;
int sum = 0;
// Let (i, j) be visited for current dfs recursion state
visited[i, j] = 1;
// Console.WriteLine(i + ", " + j);
if (i + 1 < m && j < n && visited[i + 1, j] != 1) {
sum += memo[i + 1, j] != 0 ? memo[i + 1, j] : dfs(m, n, i + 1, j);
}
if (i < m && j + 1 < n && visited[i, j + 1] != 1) {
sum += memo[i, j + 1] != 0 ? memo[i, j + 1] : dfs(m, n, i, j + 1);
}
// Set (i, j) back to un-visited for former dfs recursion state
visited[i, j] = 0;
return memo[i, j] = sum;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(mn)
其中mn是矩阵的长宽，只需要遍历一遍矩阵即可求得答案。
空间复杂度： O(mn)
其中mn是矩阵的长宽。
三、总结
这道题使用动态规划解题，重点是递归方程的推算。
回过头再看一下递归方程：
dp[i,j] = dp[i-1,j]+dp[i,j-1]
这是从左上角开始，向下或者向右移动，然后推导而来。
那么遍历方程就是从左向右，向下遍历即可。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-11-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录