FilesExpand file tree

 master

/

Solution.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

32 lines (30 loc) · 1.08 KB

 master

/

Solution.java

Copy path

Top

File metadata and controls

• Code
• Blame

32 lines (30 loc) · 1.08 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

28

29

30

31

32

package leetcode._63_;

class Solution {

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

if (obstacleGrid == null) {

return 0;

}

int m = obstacleGrid.length;

if (m == 0) {

return 0;

}

int n = obstacleGrid[0].length;

int[][] ways = new int[m][n]; // 所有的格子都能到达，因此初始化为0，表示没有计算过。该数组用于保存到达该坐标的路径个数，防止重复计算

int i = uniquePathsWithObstacles(obstacleGrid, ways, m - 1, n - 1);

return i;

}

private int uniquePathsWithObstacles(int[][] obstacleGrid, int[][] ways, int m, int n) {

if (m < 0 || n < 0 || obstacleGrid[m][n] == 1) {

return 0;

}

if (m + n == 0) {

ways[m][n] = 1;

return 1;

}

if (ways[m][n] > 0) {

return ways[m][n];

}

ways[m][n] = uniquePathsWithObstacles(obstacleGrid, ways, m, n - 1) + uniquePathsWithObstacles(obstacleGrid, ways, m - 1, n);

return ways[m][n];

}

}