Simple ✅ || Brute Force ✅-> Memoization✅ -> Tabulation✅ || Easy to Understand ✅ || beat 100% ✅
Intuition\nThe code aims to find the number of unique paths in a grid from the top-left corner to the bottom-right corner, considering certain obstacles that bl
# Intuition\nThe code aims to find the number of unique paths in a grid from the top-left corner to the bottom-right corner, considering certain obstacles that block the path. The grid is represented by a 2D matrix, where each cell can either be empty (0) or contain an obstacle (1). The problem can be solved using dynamic programming to efficiently compute the number of unique paths.\nSure, let\'s split the Approach section into three parts: Brute Force, Memoization, and Tabulation, along with their respective complexities.\n\n# Brute Force Approach\nThe brute force approach is implemented using the `solve` function, which is a recursive function exploring all possible paths from the top-left to the bottom-right corner. The function backtracks and explores the right and down directions to reach the destination while avoiding obstacles.\n\n## Complexity\n- Time complexity: The time complexity for the brute force approach is exponential, i.e., O(2^n), where n is the number of cells in the grid. This is because each cell has two choices (right or down), and the function explores all possible paths.\n- Space complexity: The space complexity for the brute force approach is O(n) due to the recursive call stack.\n\n# Code\n```\n    int solve(int i, int j, vector<vector<int>>&oG){\n        if(i>=oG.size()||j>=oG[0].size()) return 0;\n        if(oG[i][j]==1) return 0;\n        if(i==oG.size()-1 && j==oG[0].size()-1) return 1;\n\n        int ans=0;\n        int right=0,down=0;\n        right = solve(i,j+1,oG);\n        down = solve(i+1,j,oG);\n        ans = right + down;\n        return ans;\n    }\n```\n\n# Memoization Approach\nThe memoization approach is implemented using the `solveMEM` function, which is a recursive function with memoization. It avoids redundant computations by storing the results of previously computed subproblems in a 2D memoization table (`dp`).\n\n## Complexity\n- Time complexity: The memoized approach significantly improves the time complexity by avoiding redundant computations. The time complexity becomes linear, i.e., O(m * n), where m is the number of rows and n is the number of columns in the grid.\n- Space complexity: The memoization approach uses an additional 2D memoization table (`dp`) of size O(m * n) to store results, making the space complexity O(m * n).\n\n# Code\n```\n    int solveMEM(int i, int j, vector<vector<int>>&oG,vector<vector<int>>&dp){\n        if(i>=oG.size()||j>=oG[0].size()) return 0;\n        if(oG[i][j]==1) return 0;\n        if(i==oG.size()-1 && j==oG[0].size()-1) return 1;\n\n        if(dp[i][j]!=-1) return dp[i][j];\n        int ans=0;\n        int right=0,down=0;\n        right = solveMEM(i,j+1,oG,dp);\n        down = solveMEM(i+1,j,oG,dp);\n        ans = right + down;\n        return dp[i][j]=ans;\n    }\n```\n\n# Tabulation Approach\nThe tabulation approach is implemented using the `solveTAB` function, which solves the problem using dynamic programming with tabulation. It fills a 2D table (`dp`) to store the number of unique paths for each cell in the grid, starting from the destination cell and iterating from bottom to top and from right to left.\n\n## Complexity\n- Time complexity: The tabulation approach also has a linear time complexity of O(m * n), where m is the number of rows and n is the number of columns in the grid. The function fills the table in a bottom-up manner, avoiding redundant computations.\n- Space complexity: The tabulation approach uses a 2D table (`dp`) of size O(m * n), making the space complexity O(m * n).\n\nBy using memoization or tabulation, the solution\'s time complexity is significantly reduced compared to the brute force approach, making it more efficient for larger grid sizes.\n\n# Code\n```\n    int solveTAB(vector<vector<int>>&oG){\n        vector<vector<int>>dp(oG.size()+1,vector<int>(oG[0].size(),0));\n        if(oG[oG.size()-1][oG[0].size()-1]==1) return 0;\n        dp[oG.size()-1][oG[0].size()-1]=1;\n        for(int i=oG.size()-2;i>=0;i--){\n            if(oG[i][oG[0].size()-1]!=1){\n                dp[i][oG[0].size()-1]=1;\n            }\n            else break;\n        }\n        for(int j=oG[0].size()-2;j>=0;j--){\n            if(oG[oG.size()-1][j]!=1){\n                dp[oG.size()-1][j]=1;\n            }\n            else break;\n        }\n\n        for(int i=oG.size()-2;i>=0;i--){\n            for(int j=oG[0].size()-2;j>=0;j--){\n                long long ans=0;\n                long long right=0,down=0;\n                right = dp[i][j+1];\n                down = dp[i+1][j];\n                ans = right + down;\n                if(oG[i][j]!=1)\n                    dp[i][j]=ans;\n            }\n        }\n        return dp[0][0];\n    }\n\n```\n![image.png](https://assets.leetcode.com/users/images/08e806e8-0ee1-4252-88ba-4a3b65e30ac3_1690743444.0506742.png)\n
['Dynamic Programming', 'Recursion', 'Memoization', 'Matrix', 'C++']