计算机科学基础leetcode刷题动态规划
Source
Edit
History

63. 不同路径 II

Problem: 63. 不同路径 II

解题方法

  • 唯一与上一道题目不同的地方就是,添加了障碍

  • 在初始化的时候和递推公式式中稍作处理就可以了

  • 初始化的时候:只有非障碍时才继续初始化为1否则不初始化了默认为0

  • 在递推公式中:只有非障碍才计算

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
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

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int m = obstacleGrid.size();

        int n = obstacleGrid[0].size();

        vector<vector<int>> dp(m, vector(n, 0));

        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)

            dp[i][0] = 1;

        for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++)

            dp[0][i] = 1;

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {

                if (obstacleGrid[i][j] == 0) {

                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

                }

            }

        }

        return dp[m - 1][n - 1];

    }

};