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 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。