登陆空间商网站,各类网站建设,建网站怎么赚流量,idc销售网站php源码62.不同路径 题目链接#xff1a;62. 不同路径 - 力扣#xff08;LeetCode#xff09; 讲解链接#xff1a;代码随想录 动态规划五步走
1 定义dp数组是到dp[i][j]时有dp[i][j]条路径
dp[i][j] #xff1a;表示从#xff08;0 #xff0c;0#xff09;出发#xf… 62.不同路径 题目链接62. 不同路径 - 力扣LeetCode 讲解链接代码随想录 动态规划五步走
1 定义dp数组是到dp[i][j]时有dp[i][j]条路径
dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。
2 找递推公式
从题目中知道 dp[i][j]只能从上方或者左方来 所以当前路径数 上方路径数 左方路径数
就是这一行 dp[i][j] dp[i - 1][j] dp[i][j - 1];
3 初始化dp 因为只能向下或者向左走 那其实在0行i列和0行j列都只能从起点开始并且到达当前位置的路径只能是1 所以 dp[0][j] 1; dp[i][0] 1;
4 确定遍历顺序 那就直接从前往后 有固定值 也不会有空值
5 推导一下 发现结果如图代码随想录
Java代码
class Solution{public static 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 i 0; i n; i){dp[0][i] 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];}
} 63. 不同路径 II 题目链接 讲解链接 和上题思路一致 但是需要考虑障碍物位置
障碍物在 起点 在 终点 在 遍历过程中的情况 grid[i][j] 1代表当前位置有障碍物
一旦有 则 在初始化dp[0][j] 和 dp[i][0]第一行和第一列的值需要停下 而且在其障碍物以后的路径数为0
在递推公式里加了判断当前位置是否为障碍物 dp[i][j] (grid[i][j] 0) ? dp[i - 1][j] dp[i][j - 1] : 0; Java代码
class Solution{public int uniquePathsWithObstacles(int[][] grid){int m grid.length;int n grid[0].length;int[][] dp new int[m][n];//如果在起点或终点出现障碍 直接返回0if(grid[m - 1][n - 1] 1 || grid[0][0] 1){return 0;}for(int i 0; i m grid[i][0] 0; i){dp[i][0] 1;}for(int j 0; j n grid[0][j] 0; j){dp[0][j] 1;}for(int i 1; i m; i){for(int j 1; j n; j){dp[i][j] (grid[i][j] 0) ? dp[i - 1][j] dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
} 打卡打卡
