LeetCode 63. Unique Paths II
2020-06-02 19:16:43 # leetcode # dynamic programming

Problem

LeetCode 63. Unique Paths II

1. 题目简述

一个机器人坐落在一个网格中，初始点在top-left，终点在bottom-right，机器人只能向右或者向下走，而且存在一些路障（数值为1），求问有多少种走法可以到达终点。

2. 算法思路

参考解法：花花酱LeetCode

是LeetCode 62. Unique Paths进阶问题，思路类似。

动态规划

和之前思路类似，只是base case中，如果出现了路障，则后面是0。而且在动态规划递推的过程中，对于grid值为1的点dp值直接置为0。

时间复杂度:O(m * n)

空间复杂度:O(m * n)

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    // top-down
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // without padding
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        // initialize the base cases.
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
        }

        int value = 1;
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                value = 0;
            }
            dp[0][j] = value;
        }
        value = 1;
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                value = 0;
            }
            dp[i][0] = value;
        }

        return helper(obstacleGrid, dp, m - 1, n - 1);

    }

    private int helper(int[][] grid, int[][] dp, int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        if (grid[m][n] == 1) {
            return 0;
        }
        if (dp[m][n] != -1) {
            return dp[m][n];
        }

        dp[m][n] = 0;
        dp[m][n] += helper(grid, dp, m - 1, n);
        dp[m][n] += helper(grid, dp, m, n - 1);

        return dp[m][n];
    }
}
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
33
34
35
36
37
38
39
40

class Solution {
    // bottom-up
    public int uniquePaths(int m, int n) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        // initialize the base cases.
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
        }

        int value = 1;
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                value = 0;
            }
            dp[0][j] = value;
        }
        value = 1;
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                value = 0;
            }
            dp[i][0] = value;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}
Prev
2020-06-02 19:16:43 # leetcode # dynamic programming
Next