My simple and easy solution with DP using C++
My idea is inspired by the Unique Paths question, and the dynamic Programming thought. Everytime we want to calculate, just think about last time how we get the
My idea is inspired by the Unique Paths question, and the dynamic Programming thought. Everytime we want to calculate, just think about last time how we get there, and how many ways to get there.\n\nI add a `vector<vector<long> > dp(row, vector<long>(col, 0));` to store the numbers of the way to reach the point. For example, `dp[4][3] = 6;` means we have  6 ways to reach the `obstacleGrid[4][3]`.\n\nIn this question, robots only can move down or move right. Each time moves one point. When we are in `obstacleGrid[i - 1][j]`, we can **move down** to reach `obstacleGrid[i][j]`; or if we are in `obstacleGrid[i][j - 1]`, we can **move right** to reach `obstacleGrid[i][j]`. \n\nThere\'s two ways to reach `obstacleGrid[i][j]`, move down or move right. If we want to calculate the number of ways to reach `obstacleGrid[i][j]`, we only need to know the number of the ways to reach `obstacleGrid[i - 1][j]` and `obstacleGrid[i][j - 1]`.\n\nSo, easy to find the relationship below:\n`dp[i][j] = dp[i - 1][j] + ap[i][j - 1];`\n(Assumed all the i and j above is valid.)\n\nHere is my code:\n```\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        // just because obstacleGrid is too long to type\n        vector<vector<int> >& t = obstacleGrid;\n        int row = t.size(), col = t[0].size();\n        vector<vector<long> > dp(row, vector<long>(col, 0));\n        dp[0][0] = (t[0][0] == 1 ? 0 : 1);\n        // 1. calculate the first column\n        for (int i = 1; i < row; ++i) \n            dp[i][0] = (t[i][0] == 0 && dp[i - 1][0] > 0 ? 1 : 0);\n        // 2. calculate the first row\n        for (int i = 1; i < col; i++) \n            dp[0][i] = (t[0][i] == 0 && dp[0][i - 1] > 0 ? 1 : 0);\n        // 3. calculate the rest of the Grid\n        for (int i = 1; i < row; ++i) \n            for (int j = 1; j < col; ++j) \n                dp[i][j] = (t[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]);            \n        return dp[row - 1][col - 1];\n    }    \n};\n```\n\n![image](https://assets.leetcode.com/users/rsonghao/image_1555904198.png)\n\nIf we have  a 5 * 5 obstacle grid, the order of the calculation is like the picture above.\n\n![image](https://assets.leetcode.com/users/rsonghao/image_1555904508.png)\n\nFirst, make sure whether the starting point has a obstacle or not. \n\n![image](https://assets.leetcode.com/users/rsonghao/image_1555905008.png)\n![image](https://assets.leetcode.com/users/rsonghao/image_1555905057.png)\n\nThen, calculate the first row and the first column.\n\n![image](https://assets.leetcode.com/users/rsonghao/image_1555905218.png)\n\nAt last, calculate the rest of the obstacle grid.\n\n\n\n\n\n\n\n
['Dynamic Programming', 'C++']