✅C++ || Easy (Recursion + DP) || Simple || 🗓️ Daily LeetCoding Challenge May, Day 20
Please Upvote If It Helps\n\n\nclass Solution {\npublic:\n    int dfs(vector<vector<int>>& obstacleGrid,int i,int j,vector<vector<int>> &dp,int m ,int n)\n    {
**Please Upvote If It Helps**\n\n```\nclass Solution {\npublic:\n    int dfs(vector<vector<int>>& obstacleGrid,int i,int j,vector<vector<int>> &dp,int m ,int n)\n    {\n        // if current cell value is not inside the boundary then we can not proceed further return 0\n        if(i<0 || j<0 || i>=m || j>=n || obstacleGrid[i][j]==1)\n            return 0;\n        \n        // if we have already computed the value then no need to calvulate it again\n        if(dp[i][j]!=-1)\n        {\n            return dp[i][j];\n        }\n        \n        // if we have on last cell then tsake it as a path and return 1\n        if(i==m-1 && j==n-1)\n        {    \n            return 1;\n        }\n        \n        // now call the same function for right move and down move and add that\n        // first this function will go for the right move and calculate it paths\n        // then after backtrack it will go to down and calculate their paths\n        // and at the end add up both the paths and return\n        //                      (right move)             (down move)\n        return dp[i][j]=dfs(obstacleGrid,i,j+1,dp,m,n)+dfs(obstacleGrid,i+1,j,dp,m,n);\n    }\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) \n    {\n        int m=obstacleGrid.size();      // no. of rows\n        int n=obstacleGrid[0].size();   // no. of columns\n        \n        // set all values as -1 for dp\n        vector<vector<int>> dp(m,vector<int>(n,-1));\n        \n        // return the possible paths\n        return dfs(obstacleGrid,0,0,dp,m,n);   \n    }\n};\n```
[]