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

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

一、62.不同路径

题目链接：https://leetcode.cn/problems/unique-paths/
思路：dp[i][j]表示从（0,0）到[i,j]有dp[i][j]种路线，因为每次只能往右走一步或者往下走一步，达到[i][j]只能从[i-1][j]和[i][j-1]，那么dp[i][j]=dp[i-1][j]+dp[i][j-1]，初始化第一行第一列都是1，遍历从左往右从上往下。

class Solution {
   public int uniquePaths(int m, int n) {
        int[][] nums = new int[m][n];
        for (int i = 0; i < m; i++) {
            nums[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            nums[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                nums[i][j] = nums[i-1][j] + nums[i][j-1];
            }
        }
        return nums[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、63. 不同路径 II

题目链接：https://leetcode.cn/problems/unique-paths-ii/
思路：思路和上面的题目一样，初始化时遇到石头立刻终止，遍历计算dp[i][j]遇到石头时跳过。

class Solution {
     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] nums = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) break;
            nums[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) break;
            nums[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                nums[i][j] = nums[i-1][j] + nums[i][j-1];
            }
        }
        return nums[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21