广西网站建设电话,江苏建设类专业技术人员资格考试,揭阳建站服务,ppt模板免费背景算法-DFS记忆化/动态规划-不同路径 II
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/unique-paths-ii
1.2 题目描述 2 DFS记忆化
2.1 思路
注意题意#xff0c;每次要么往右#xff0c;要么往下走#xff0c;也就是说不能走回头路。但是仍有可能走到之前已经…算法-DFS记忆化/动态规划-不同路径 II
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/unique-paths-ii
1.2 题目描述 2 DFS记忆化
2.1 思路
注意题意每次要么往右要么往下走也就是说不能走回头路。但是仍有可能走到之前已经访问过的节点。题意是要求走到终点的路径数假设往右可以走通往下也可以走通那么当前格子的走通方法数 往右走通方法数 往下走通方法数。
2.2 代码
class Solution {int m 0;int n 0;int[][] paths null;public int uniquePathsWithObstacles(int[][] obstacleGrid) {m obstacleGrid.length;n obstacleGrid[0].length;paths new int[m][n];return dfs(obstacleGrid, 0, 0);} private int dfs(int[][] obstacleGrid, int i, int j) {if (paths[i][j] 0) {return paths[i][j];}if (obstacleGrid[i][j] 1) {return 0;}if (i m - 1 j n - 1) {paths[i][j] 1;return 1;}int result 0;if (i m - 1) {result dfs(obstacleGrid, i 1, j);}if (j n - 1) {result dfs(obstacleGrid, i, j 1);}paths[i][j] result;return result;}
}2.3 时间复杂度
O(m*n)
2.4 空间复杂度
O(m*n)
3 二维动态规划
3.1 思路
从上述DFS中思考可以推出动态规划表达式dp[i][j] dp[i1][j] dp[i][j1]。
这里注意两点
dp[m-1][n-1] 的值需要看obstacleGrid[m-1][n-1]是否为1如果为1代表是障碍则直接就返回0了。否则就填为1.从动态规划表达式可知需要i和j都从大到小遍历才可计算。
3.2 代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;if (n 0) {return 1;}if (obstacleGrid[m - 1][n - 1] 1) {return 0;}// dp[i][j] dp[i1][j] dp[i][j1]int[][] dp new int[m][n];dp[m-1][n-1] 1;for (int i m - 1; i 0; i--) {for (int j n - 1; j 0; j--) {if (obstacleGrid[i][j] 1) {dp[i][j] 0;continue;}if (i m - 1) {dp[i][j] dp[i1][j];}if (j n - 1) {dp[i][j] dp[i][j1];}}}return dp[0][0];}
}3.3 时间复杂度 O(M*N)
3.4 空间复杂度
O(M*N)
4 一维动态规划
4.1 思路
尝试压缩为一维动态规划。
考虑dp[i][j] dp[i1][j] dp[i][j1]那么如果我们每次固定i值从最后一行的j从大到小递减计算就能计算出最后一行的各个dp[j]值。然后i-1到上一行此时dp[j]依然表示此行每个位置的通终点方法数相当于是已经从当前位置累加了往下走的路线的方法数即dp[i][j] dp[i1][j] dp[i][j1]中的 dp[i1][j]那么我们只需要再计算本行的dp[i][j1]即可。综上所述我们可以压缩二维动态规划为一维动态规划dp[j] dp[j1]
4.2 代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;if (n 0) {return 1;}if (obstacleGrid[m - 1][n - 1] 1) {return 0;}int[] dp new int[n];dp[n-1] 1;for (int i m - 1; i 0; i--) {for (int j n - 1; j 0; j--) {if (obstacleGrid[i][j] 1) {dp[j] 0;continue;}if (j n - 1) {dp[j] dp[j1];}}}return dp[0];}
}4.3 时间复杂度 3.4 空间复杂度
O(N)
