Least Optimal To Most Optimal✅✅|| 4 Approaches🔥|| CPP
Complexity\n\n\n\n\n\n\n\n# Pure Recursion\n\nclass Solution {\npublic:\n    int solve(vector<vector<int>>& obstacleGrid,int i,int j){\n        if(i==obstacleGr
# Complexity\n![image.png](https://assets.leetcode.com/users/images/bef49e0c-9920-4e7f-9e6c-2ae11a37ced4_1721049025.9257708.png)\n\n\n\n![image.png](https://assets.leetcode.com/users/images/6a5cc911-ec1a-4256-8d63-02a808e98dd5_1721049305.0551262.png)\n\n\n# Pure Recursion\n```\nclass Solution {\npublic:\n    int solve(vector<vector<int>>& obstacleGrid,int i,int j){\n        if(i==obstacleGrid.size()-1 && j==obstacleGrid[0].size()-1 && obstacleGrid[i][j]!=1) return 1;\n        \n        if(i<0 || j<0 || i>=obstacleGrid.size() || j>=obstacleGrid[0].size() || obstacleGrid[i][j]==1) return 0;\n\n        return solve(obstacleGrid,i,j+1)+solve(obstacleGrid,i+1,j);\n    }\n\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        return solve(obstacleGrid,0,0);\n    }\n};\n```\n\n\n# Memoization\n```\nclass Solution {\npublic:\n    int solve(vector<vector<int>>& obstacleGrid,int i,int j,vector<vector<int>>&memo){\n        if(i==obstacleGrid.size()-1 && j==obstacleGrid[0].size()-1 && obstacleGrid[i][j]!=1) return 1;\n        \n        if(i<0 || j<0 || i>=obstacleGrid.size() || j>=obstacleGrid[0].size() || obstacleGrid[i][j]==1) return 0;\n\n        if(memo[i][j]!=-1) return memo[i][j];\n        return memo[i][j]=solve(obstacleGrid,i,j+1,memo)+solve(obstacleGrid,i+1,j,memo);\n    }\n\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        vector<vector<int>>memo(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),-1));\n        return solve(obstacleGrid,0,0,memo);\n    }\n};\n```\n\n# Tabulation\n```\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int r = obstacleGrid.size(), c = obstacleGrid[0].size();\n        vector<vector<long long>>dp(r,vector<long long>(c,0));\n        if(obstacleGrid[r-1][c-1]==1) return 0;\n        if(r==1 && c==1 && obstacleGrid[r-1][c-1]==0) return 1;\n\n        int k = 1;\n        dp[r-1][c-1] = 1;\n        for(int i = r-2;i>=0;i--){\n            if(obstacleGrid[i][c-1]==1) k = 0;\n            dp[i][c-1] = k;\n        }\n        k = 1;\n        for(int j = c-2;j>=0;j--){\n            if(obstacleGrid[r-1][j]==1) k = 0;\n            dp[r-1][j] = k;\n        }\n\n        for(int i = r-2;i>=0;i--){\n            for(int j= c-2;j>=0;j--){\n                if(obstacleGrid[i][j]==0){\n                    dp[i][j]= dp[i][j+1] + dp[i+1][j];\n                }\n                else dp[i][j] = 0;\n            }\n        }\n        \n        return dp[0][0];\n    }\n};\n```\n\n# Tabulation With Space Optimization\n```\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int r = obstacleGrid.size(), c = obstacleGrid[0].size();\n        if(obstacleGrid[r-1][c-1]==1) return 0;\n        if(r==1 && c==1 && obstacleGrid[r-1][c-1]==0) return 1;\n\n        int k = 1;\n        for(int i = r-2;i>=0;i--){\n            if(obstacleGrid[i][c-1]==1){\n                obstacleGrid[i][c-1] = 0;\n                k = 0;\n            }\n            obstacleGrid[i][c-1] = k;\n        }\n        k = 1;\n        for(int j = c-2;j>=0;j--){\n            if(obstacleGrid[r-1][j]==1){\n                obstacleGrid[r-1][j] = 0;\n                k = 0;\n            }\n            obstacleGrid[r-1][j] = k;\n        }\n\n        for(int i = r-2;i>=0;i--){\n            for(int j= c-2;j>=0;j--){\n                if(obstacleGrid[i][j]==0){\n                    obstacleGrid[i][j] = obstacleGrid[i][j+1]>INT_MAX-obstacleGrid[i+1][j] ? INT_MAX : obstacleGrid[i][j+1]+obstacleGrid[i+1][j];\n                }\n                else obstacleGrid[i][j] = 0;\n            }\n        }\n        return obstacleGrid[0][0];\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'Recursion', 'Memoization', 'C++']