网站怎么做话术,南京林业大学实验与建设网站,小程序打包成app,收录是什么意思目录
力扣62. 不同路径
解析代码1_暴搜递归#xff08;超时#xff09;
解析代码2_记忆化搜索
解析代码3_动态规划 力扣62. 不同路径
62. 不同路径
难度 中等
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器…目录
力扣62. 不同路径
解析代码1_暴搜递归超时
解析代码2_记忆化搜索
解析代码3_动态规划 力扣62. 不同路径
62. 不同路径
难度 中等
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1 输入m 3, n 7
输出28
示例 2
输入m 3, n 2
输出3
解释
从左上角开始总共有 3 条路径可以到达右下角。
1. 向右 - 向下 - 向下
2. 向下 - 向下 - 向右
3. 向下 - 向右 - 向下示例 3
输入m 7, n 3
输出28示例 4
输入m 3, n 3
输出6提示
1 m, n 100题目数据保证答案小于等于 2 * 10^9
class Solution {
public:int uniquePaths(int m, int n) {}
}; 解析代码1_暴搜递归超时
递归含义给 dfs 一个下标返回从 [0, 0] 位置走到 [i, j] 位置一共有多少种方法。函数体只要知道到达上面位置的方法数以及到达左边位置的方法数然后累加起来即可。递归出口当下标越界的时候返回 0 当位于起点的时候返回 1 。
class Solution {
public:int uniquePaths(int m, int n) {return dfs(m, n);}int dfs(int sr, int sc){if(sr 0 || sc 0)return 0;if(sr 1 sc 1)return 1;return dfs(sr - 1, sc) dfs(sr, sc - 1);}
}; 解析代码2_记忆化搜索
记忆化搜索解法
加上一个备忘录。每次进入递归的时候去备忘录里面看看。每次返回的时候将结果加入到备忘录里面。
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint memo(m 1, vectorint(n 1));return dfs(m, n, memo);}int dfs(int sr, int sc, vectorvectorint memo){if(sr 0 || sc 0)return 0;if(sr 1 sc 1)return 1;if(memo[sr][sc] ! 0)return memo[sr][sc];memo[sr][sc] dfs(sr - 1, sc, memo) dfs(sr, sc - 1, memo);return memo[sr][sc];}
};解析代码3_动态规划
根据记忆化搜索得出动态规划的解法
递归含义状态表示函数体状态转移方程递归出口初始化填表顺序填备忘录的顺序返回值备忘录的值
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m 1, vectorint(n 1, 0));dp[1][1] 1;for(int i 1; i m; i){for(int j 1; j n; j){if(i 1 j 1)continue;dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m][n];}
};
