Ming
0%

Leetcode-63

Posted on Edited on In

Leetcode-63 不同路径II

题目

结果

代码

版本一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 用两个变量存储行数和列数
        int row = obstacleGrid.length, column = obstacleGrid[0].length;
        // path[i][j]代表从起点到（i，j）的路径数
        int[][] path = new int[row][column];
        // 初始条件
        path[0][0] = 1;
        // 遍历path
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                // 障碍物
                if (obstacleGrid[i][j] == 1) {
                    path[i][j] = 0;
                } else {
                    if (i >= 1) {
                        path[i][j] += path[i - 1][j];
                    }
                    if (j >= 1) {
                        path[i][j] += path[i][j - 1];
                    }
                }
            }
        }
        return path[row - 1][column - 1];
    }
}

版本二（优化版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 用两个变量存储行数和列数
        int row = obstacleGrid.length, column = obstacleGrid[0].length;
        // path[i]代表从起点到第i个位置的路径数
        int[] path = new int[column];
        // 初始条件
        path[0] = 1;
        // 遍历path
        for (int[] rows : obstacleGrid) {
            for (int j = 0; j < column; j++) {
                // 障碍物
                if (rows[j] == 1) {
                    path[j] = 0;
                } else {
                    if (j >= 1) {
                        path[j] += path[j - 1];
                    }
                }
            }
        }
        return path[column - 1];
    }
}