描述

63. 不同路徑II
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

思路一：動態(tài)規(guī)劃

• 1：確定dp數(shù)組與下標(biāo)的含義
  dp[i][j]:表示從(0,0)出發(fā)，到(i,j)有dp[i][j]條不同的路徑
• 2：確定了遞推公式
  遞推公式和62.不同路徑一樣，d[i][j]=dp[i-1][j]+dp[i][j-1]
  但是需要注意因為有了障礙，如果是障礙的話就保持初始狀態(tài)。
• 3：dp數(shù)組初始化
  因為從(0, 0)的位置到(i, 0)的路徑只有?條，所以dp[i][0]?定為1， dp[0][j]也同理。
  但如果(i, 0) 這條邊有了障礙之后，障礙之后（包括障礙）都是?不到的位置了，所以障礙之后的dp[i][0]
  應(yīng)該還是初始值0。

class Solution { public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//獲取行列大小int m = obstacleGrid.size();int n = obstacleGrid[0].size();//定義一個二維dp[i][j]數(shù)組,代表到i,j時候的路徑數(shù)vector<vector<int> > dp(m,vector(n,0)); //dp初始化for(int i=0;i<m&&obstacleGrid[i][0]==0;i++) dp[i][0] = 1;for(int j=0;j<n&&obstacleGrid[0][j]==0;j++) dp[0][j] = 1;//遍歷for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-动态规划基础题-63. 不同路径II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。