跳转至

63 不同路径II

深搜(超时)

class Solution {
private:
    int dfs(vector<vector<int>>& obstacleGrid, int i, int j){
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        // obstacleGrid[i][j] == 1直接返回0
        if(i >= m || j >= n || obstacleGrid[i][j] == 1)  return 0;
        if(i == m - 1 && j == n - 1 && obstacleGrid[i][j] == 0)    return 1;
        return dfs(obstacleGrid, i + 1, j) + dfs(obstacleGrid, i, j + 1);
    }
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        return dfs(obstacleGrid,0, 0);
    }
};

动态规划

初始化的时候注意

obstacleGrid[i][0] == 0说明dp[i + 1][0] == 0及之后的dp[i][0]都为0

二维做法

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 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];
                else
                    dp[i][j] = 0;
            }
        }
        return dp[m - 1][n - 1];
    }
};

一维优化

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int> dp(n, 0);
        // 这里不仅把dp[0][j]都初始化为1
        // 而且把dp[i][0](i == 0)初始化为1
        // 在之后的循环中,如果obstacleGrid[i][0] == 0那么dp[i][0]将一直保持为1
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[j] = 1;
        for(int i = 1; i < m; i++){
            // 这里必须从j == 0开始
            // 因为如果obstacleGrid[i][0] == 1,需要将dp[i][0]更改状态为0
            // 一旦更改状态为0后,之后将一直保持状态为0
            for(int j = 0; j < n; j++){
                if(obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else if(j != 0)
                    dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};