✅C++ | ✅2 Approaches | ✅Recusion and Bottom-up Approach | ✅Use DP | ✅Explanation with comments
Please upvote if you find this solution helpful ;)\n\nApproach-1 : Use recursion and dynamic programming\nTC- O(MxN), recursion \nSC- O(MxN), dp/mxn matrix\nAux
**Please upvote if you find this solution helpful ;)**\n\n**Approach-1 : Use recursion and dynamic programming\nTC- O(MxN), recursion \nSC- O(MxN), dp/mxn matrix\nAuxiliary Space - O(M+N), recursion call**\n\n```\n//We can use recursion but it takes too much time and we get TLE\n//So, we implement dynamic programming with recursion/dp\nclass Solution {\npublic:\n    \n    int findPath(int r, int c, vector<vector<int>>& grid, vector<vector<int>>& dp)\n    {\n        //boudary and obstacle condition\n        if(r>=grid.size() || c>=grid[0].size() || grid[r][c]==1) return 0;\n        \n        //if we reach right bottom, we get 1 path and return it\n        if(r==grid.size()-1 && c==grid[0].size()-1) return 1;\n        \n        //if path is already store in dp we return it\n        if(dp[r][c]!=-1) return dp[r][c];\n        \n        //calculate the no. of path by moving down and right and return it\n        //and store it into the dp\n        return dp[r][c]= (findPath(r+1, c, grid, dp) + findPath(r, c+1, grid, dp));\n    }\n    \n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) \n    {\n        int m = obstacleGrid.size(), n=obstacleGrid[0].size();\n        vector<vector<int>> dp(m, vector<int> (n, -1)); //create mxn matrix dp and initialize it with -1\n        return findPath(0,0, obstacleGrid, dp); calling the function to find no. of unique path\n    }\n};\n```\n\n**Approach-2 : Use bottom-up approach and dynamic programming\nTC- O(MxN), iteration \nSC- O(MxN), dp/mxn matrix**\n\n```\n//Use bottom-up approach to save the auxiliary space taken by recursion\nclass Solution {\npublic:\n    \n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) \n    {\n        //if top-left corner has value 1 it means there in no path\n        if(obstacleGrid[0][0]==1) return 0;\n        \n        //store no. of rows and columns\n        int m = obstacleGrid.size(), n=obstacleGrid[0].size();\n        \n        //create dp and initialize it with 0\n        vector<vector<int>> dp(m, vector<int> (n, 0));\n        \n        //base condition for bottom-up approach\n        dp[0][0] = 1;\n        \n        //traverse through the matrix\n        for(int i=0; i<m; i++)\n        {\n            for(int j=0; j<n; j++)\n            {\n                //if we are at top-left corner(0,0) we don\'t have left(0,-1) and up(-1,0,) cell\n                //so to avoid this condition we continue at 0,0\n                if(i==0 && j==0) continue;\n                \n                //if there is no obstacle\n                if(obstacleGrid[i][j]==0)\n                {\n                    int up=0, left=0;\n\n                    //store top cell value\n                    if(i-1 >=0)\n                        up = dp[i-1][j];\n\n                    //store left cell value\n                    if(j-1 >=0)\n                        left = dp[i][j-1];\n                \n                    //and add them for current cell to get no. of unique paths \n                    //to reach at current position\n                    dp[i][j] = up + left;\n                }\n            }\n        }\n        //return dp at (m-1, n-1) that will be the no. of unique paths\n        //to reach at bottom right corner\n        return dp[m-1][n-1];\n         \n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'Iterator', 'C++']