63. Unique Paths II 动态规划

description:

https://leetcode.com/problems/unique-paths/
机器人从一堆方格的左上角走到右下角，只能往右或者往下走 ，问有几种走法，这个加了难度，在矩阵中加了障碍物
Note:

Example:

Example 1:Input: [[0,0,0],[0,1,0],[0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

answer:

class Solution { public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<vector<long>> dp(m + 1, vector<long>(n + 1, 0)); //比实际大一圈是为了处理左边和上边两个边的边缘问题dp[0][1] = 1; // 初始化for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (obstacleGrid[i - 1][j - 1] != 0) continue; //如果是障碍则略过dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];} };

relative point get√：

hint :

动态规划

转载于:https://www.cnblogs.com/forPrometheus-jun/p/11336701.html

总结

以上是生活随笔为你收集整理的63. Unique Paths II 动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。