Share my 6-line DP C++ solution (with ONE vector & NO special cases)


  • 0
    S

    The idea is to add an extra "all-zero row" and "all-zero column" on the top/leftmost.

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

Log in to reply
 

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