C++ recursive DP->1D DP||Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is a DP question. Use DP in a standard way!\n# Approach\n Describe your approach t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is a DP question. Use DP in a standard way!\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThere is a similar question which can be solved by using Pascal traingle.\n[Leetcode 62. Unique Paths](https://leetcode.com/problems/unique-paths/solutions/3602735/python-c-solutions-use-math-pascal-triangle-dp-beats-100/)\n\nBut in this question there are so many obstacleGrids, the direct applying of Math trick like Pascal Triangle is is not easy and does not bring benefits( language like python which has packages for computing combinations). It is suggested to use standardard DP to solve.\n\nIn fact, it is not difficult to know that\n```\nif (obstacleGrid[i][j]==1) return dp[i][j]=0;\n```\nIn second approach, optimized 1D iterative DP is implemented which beats 100%.\n\nThe space complexity is reduced. Consider the transforms\n```\ndp[j]<-dp[i][j]\nprev[j]<-dp[i-1][j]\n```\nBefore the next iteration, don\'t forget ```prev=dp```! Such tricks are used  in such Pascal-triangle-like problems(Leetcode 118. Pascal\'s Triangle)\n[Please turn on English subtitles if neccessary]\n[https://youtu.be/paoJGMYEEhA](https://youtu.be/paoJGMYEEhA)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(nm)\\to O(m)$$\n# Code\n```\nclass Solution {\npublic:\n    int n, m;\n    vector<vector<long long>> dp;\n    long long numsPaths(int i, int j, vector<vector<int>>& obstacleGrid)\n    {       \n        if (dp[i][j]!=-1) return dp[i][j];\n        if (obstacleGrid[i][j]==1) return dp[i][j]=0;\n        long long ans=0;\n        if (i>0) ans+=numsPaths(i-1, j, obstacleGrid);\n        if (j>0) ans+=numsPaths(i, j-1, obstacleGrid);\n        if (i==0 && j==0) ans=(obstacleGrid[0][0]==0)?1:0;\n        return dp[i][j]=ans;     \n    }\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        n=obstacleGrid.size();\n        m=obstacleGrid[0].size();\n        dp.assign(n, vector<long long>(m, -1));\n\n        return numsPaths(n-1, m-1, obstacleGrid);\n    }\n};\n```\n# Buttom up Approach using 1D arrays beating 100%\n```\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int n=obstacleGrid.size();\n        int m=obstacleGrid[0].size();\n        vector<int> dp(m, 0), prev(m, 0);\n        \n        //Deal with 0th row \n        for(int j=0; j<m; j++){\n            if (obstacleGrid[0][j]==1) break;\n            else dp[j]=1;\n        }\n        prev=dp;\n            \n        for(int i=1; i<n; i++){\n            if (obstacleGrid[i][0]==1) dp[0]=0;\n            else dp[0]=prev[0];\n            for(int j=1; j<m; j++){\n                if (obstacleGrid[i][j]==1) dp[j]=0;\n                else dp[j]=prev[j]+dp[j-1];\n            }\n            prev=dp;\n        }\n        return dp[m-1];\n    }\n};\n```
['Dynamic Programming', 'C++']