DP solution with O(N) space, without extra bounds check


  • 1
    B
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            int m(obstacleGrid.size()), n(obstacleGrid[0].size());
            vector<int> DP(n, 0);
            DP[0] = obstacleGrid[0][0] ? 0 : 1;
            for(int i(0); i < m; ++i)
            {
                DP[0] &= !obstacleGrid[i][0];
                for(int j(1); j < n; ++j)
                {
                    DP[j] = obstacleGrid[i][j] ? 0 : DP[j - 1] + DP[j];
                }
            }
            return DP.back();
        }
    };
    

    For fist column,

    0 0 0 1 0 0 1 0 ...

    When meet first '1', the place after this '1' can be seems as obstacle:

    0 0 0 1 1 1 1 1 ...

    To avoid checking DP[0] = DP[0] + DP[0 - 1], using the code below to compute DP[0]:

    DP[0] &= !obstacleGrid[i][0];

Log in to reply
 

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