C++ DP 3ms O(n) Space


  • 0
    E
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    // parameters check
            if (obstacleGrid.empty() || obstacleGrid[0].empty()) {
                return 0;
            }
            int m = obstacleGrid.size();
            int n = obstacleGrid[0].size();
    // keep the number of unique paths for the first line.
            vector<int> path(n, 1);
    // initialize the first line path, when obstacle is encounterred, assign 0 to all the rest elements. 
            for (int i = 0; i < n; i++) {
                if (obstacleGrid[0][i] == 1) {
                    while (i < n) {
                        path[i++] = 0;
                    }
                }
            }
    // start from the second line. for each line, check if the first is obstacle, if it is, then set path[0] = 0 which means no path going down from now on.
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (j == 0) {
                        if (obstacleGrid[i][0] == 1) {
                            path[0] = 0;
                        }
                        continue;
                    }
                    if (obstacleGrid[i][j] == 1) {
                        path[j] = 0;
                    } else {
                        path[j] = path[j] + path[j - 1];
                    }
                }
            }
            return path[n - 1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.