c++ simple dp solution


  • 0
    H
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            if(obstacleGrid.empty()) return 0;
            int m = obstacleGrid.size(), n = obstacleGrid[0].size();
            vector<vector<int> > dp(m, vector<int> (n, 1));
            bool block = false; // indicate whether the edge path has been blocked
            for(int j = 0; j < n; j ++) {
                if(obstacleGrid[0][j]) block = true;
                if(block) dp[0][j] = 0;
            }
            block = false;
            for(int i = 0; i < m; i ++) {
                if(obstacleGrid[i][0]) block = true;
                if(block) dp[i][0] = 0;
            }
            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];
        }
    };
    

Log in to reply
 

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