C++ | 4 Solutions | Recursive, Memoization, Tabulation & Super Optimised
1. Recursive\n\nint path(int row, int col, vector<vector<int>>& obstacleGrid) {\n    if(row == 0 && col == 0)\n        return 1;\n    if(row < 0 || col < 0)\n  
**1. Recursive**\n```\nint path(int row, int col, vector<vector<int>>& obstacleGrid) {\n    if(row == 0 && col == 0)\n        return 1;\n    if(row < 0 || col < 0)\n        return 0;\n    if(obstacleGrid[row][col] == 1)\n        return 0;\n    int left = path(row, col - 1, obstacleGrid);\n    int up = path(row - 1, col, obstacleGrid);\n    return left + up;\n}\n\nint uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n    int row = obstacleGrid.size();\n    int col = obstacleGrid[0].size();\n    return path(row - 1, col - 1, obstacleGrid);\n}\n```\n\n**2. Memoization**\n```\nint path(int row, int col, vector<vector<int>>& obstacleGrid, vector<vector<int>> &dp) {\n    if(row == 0 && col == 0)\n        return 1;\n    if(row < 0 || col < 0)\n        return 0;\n    if(obstacleGrid[row][col] == 1)\n        return 0;\n    if(dp[row][col] != -1)\n        return dp[row][col];\n    \n    int left = path(row, col - 1, obstacleGrid, dp);\n    int up = path(row - 1, col, obstacleGrid, dp);\n    return dp[row][col] = left + up;\n}\n\nint uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n    if(obstacleGrid[0][0] == 1) return 0;\n    \n    int row = obstacleGrid.size();\n    int col = obstacleGrid[0].size();\n    vector<vector<int>> dp(row, vector<int> (col, -1));\n    return path(row - 1, col - 1, obstacleGrid, dp);\n}\n```\n\n**3. Tabulation**\n```\nint uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n    if(obstacleGrid[0][0] == 1) return 0;\n    \n    int row = obstacleGrid.size();\n    int col = obstacleGrid[0].size();\n    vector<vector<int>> dp(row, vector<int> (col, -1));\n    \n    for(int i = 0; i < row; i++) {\n        for(int j = 0; j < col; j++) {\n            if(i == 0 && j == 0) dp[i][j] = 1;\n            else if(obstacleGrid[i][j] == 1) dp[i][j] = 0;\n            else {\n                int left = 0, up = 0;\n                if(i > 0) up = dp[i - 1][j];\n                if(j > 0) left = dp[i][j - 1];\n                dp[i][j] = left + up;\n            }\n        }\n    }\n    return dp[row - 1][col - 1];\n}\n```\n\n**4. Tabulation + More Space Optimised**\n```\nint uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n    if(obstacleGrid[0][0] == 1) return 0;\n    \n    int row = obstacleGrid.size();\n    int col = obstacleGrid[0].size();\n    vector<int> prevRow(col, 0);\n    \n    for(int i = 0; i < row; i++) {\n        vector<int> temp(col, 0);\n        for(int j = 0; j < col; j++) {\n            if(i == 0 && j == 0) temp[j] = 1;\n            else if(obstacleGrid[i][j] == 1) temp[j] = 0;\n            else {\n                int left = 0, up = 0;\n                if(i > 0) up = prevRow[j];\n                if(j > 0) left = temp[j - 1];\n                temp[j] = left + up;\n            }\n        }\n        prevRow = temp;\n    }\n    return prevRow[col - 1];\n}\n```
['Dynamic Programming', 'Recursion']