代码随想录训练营第三十四天| 62.不同路径 63. 不同路径 II

 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];}
}

 打卡打卡