問題描述

一個機器人位于一個 m x n 網(wǎng)格的左上角 (起始點在下圖中標記為“Start” )。

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

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

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

說明：m 和 n 的值均不超過 100。

示例 1:

輸入:

[

[0,0,0],

[0,1,0],

[0,0,0]

]

輸出: 2

解釋:

3x3 網(wǎng)格的正中間有一個障礙物。

從左上角到右下角一共有 2 條不同的路徑：

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

動態(tài)規(guī)劃解決

前面我們講過的409，動態(tài)規(guī)劃求不同路徑和這非常類似的一道題，只不過上一篇沒有障礙物，但并不影響我們解這道題，我們還用dp[i][j]表示到坐標(i，j)這個格內(nèi)有多少條不同的路徑，所以最終的答案就是求dp[m-1][n-1]。

這里的遞推分為兩種情況，一種是當前網(wǎng)格沒有障礙物，一種是當前網(wǎng)格有障礙物。

1，如果當前網(wǎng)格dp[i][j]有障礙物，那么這里肯定是走不過去的，所以dp[i][j]=0。

2，如果當前網(wǎng)格dp[i][j]沒有障礙物，那么遞推公式就和上一題409，動態(tài)規(guī)劃求不同路徑一樣了。

因為只能從上面或左邊走過來，所以遞推公式是

dp[i][j]=dp[i-1][j]+dp[i][j-1]。

• dp[i-1][j]表示的是從上面走過來的路徑條數(shù)。
• dp[i][j-1]表示的是從左邊走過來的路徑條數(shù)。

邊界條件也好判斷，如果當前行沒有障礙物，那么當前行的值都是1，如果有障礙物，那么第一個障礙物前面都是1，其他的都是0。同理第一列也一樣。

我們來看下代碼

public?int?uniquePathsWithObstacles(int[][]?obstacleGrid)?{????int?m?=?obstacleGrid.length;????int?n?=?obstacleGrid[0].length;????int?dp[][]?=?new?int[m][n];????//第一列初始化????for?(int?i?=?0;?i?

代碼和409，動態(tài)規(guī)劃求不同路徑差不多，只不過在第一行和第一列還有上面第21行多了一些判斷。

動態(tài)規(guī)劃代碼量優(yōu)化

上面代碼雖然也能實現(xiàn)，但有那么多條件判斷總感覺很繁瑣，所以我們還有一種方式就是把二維數(shù)組的長和寬都放大一格，這樣數(shù)組的第一行和第一列都不存儲任何值，但初始條件要變了

• dp[1][1] = obstacleGrid[0][0] ^ 1;
• dp[0][1] = 1;
• dp[1][0] = 1;

上面3種初始條件都可以，我們來任選一個，看下代碼

public?int?uniquePathsWithObstacles(int[][]?obstacleGrid)?{????int?m?=?obstacleGrid.length;????int?n?=?obstacleGrid[0].length;????int?dp[][]?=?new?int[m?+?1][n?+?1];????//初始條件，下面3個任選一個????//dp[1][1]?=?obstacleGrid[0][0]?^?1;????//dp[0][1]?=?1;????dp[1][0]?=?1;????for?(int?i?=?1;?i?<=?m;?++i)????????for?(int?j?=?1;?j?<=?n;?++j)????????????if?(obstacleGrid[i?-?1][j?-?1]?==?0)????????????????dp[i][j]?+=?dp[i?-?1][j]?+?dp[i][j?-?1];????return?dp[m][n];}

動態(tài)規(guī)劃空間優(yōu)化

我們可以參照上一題把二維空間改為一維的，原理很簡單，我們來直接看代碼

public?int?uniquePathsWithObstacles(int[][]?obstacleGrid)?{????int?m?=?obstacleGrid.length;????int?n?=?obstacleGrid[0].length;????int[]?dp?=?new?int[n?+?1];????dp[1]?=?1;????for?(int?i?=?0;?i?

上一題有人問過一個問題說看不懂第11行，這里再說一下，因為是一行一行的遍歷，在當前行遍歷之前dp(這里是一維數(shù)組)表示的是上一行的值，然后遍歷到當前行的時候，假如遍歷當前行的第j列的時候，那么當前行第j列之前的數(shù)據(jù)都會被更新掉，當前行第j列之后的數(shù)據(jù)還是上一行的，所以dp[j]=dp[j]+dp[j-1](為了區(qū)分，這里標成了不同的顏色)，dp[j]表示的是當前列的上一行值，dp[j-1]表示的是當前行的前一個值。

遞歸方式

上一題我們提到過，使用遞歸的方式會造成大量的重復計算，所以為了減少重復計算，這里使用一個map把計算過的值存儲起來，下次用的時候先從map中取，如果有就返回，如果沒有再計算。

public?int?uniquePathsWithObstacles(int[][]?obstacleGrid)?{????return?helper(obstacleGrid,?0,?0,?new?HashMap());}public?static?int?helper(int[][]?obstacleGrid,?int?down,?int?right,?Map?map)?{????String?key?=?down?+?"and"?+?right;????int?result?=?0;????if?(map.containsKey(key))????????return?map.get(key);????if?(obstacleGrid[down][right]?==?1)?{????????result?=?0;????????map.put(key,?result);????????return?result;????}????if?(right?==?obstacleGrid[0].length?-?1?&&?down?==?obstacleGrid.length?-?1)?{????????if?(obstacleGrid[down][right]?==?1)?{????????????result?=?0;????????}?else?{????????????result?=?1;???????}????????map.put(key,?result);????????return?result;????}????if?(right?==?obstacleGrid[0].length?-?1?||?down?==?obstacleGrid.length?-?1)?{????????if?(right?==?obstacleGrid[0].length?-?1)?{????????????result?=?helper(obstacleGrid,?down?+?1,?right,?map);????????}?else?{????????????result?=?helper(obstacleGrid,?down,?right?+?1,?map);????????}????????map.put(key,?result);????????return?result;????}????result?=?helper(obstacleGrid,?down,?right?+?1,?map)?+?helper(obstacleGrid,?down?+?1,?right,?map);????map.put(key,?result);????return?result;}

這種不看也可以，因為動態(tài)規(guī)劃非常簡單，沒人會傻到會使用這種方式，但他也算是提供了一種思路，有時間看看也行。

總結(jié)

這題多了一個障礙物的判斷，但難度其實并沒有增加多少，如果當前位置出現(xiàn)了障礙物，說明不能從當前位置通過，所以當前位置的路徑是0，如果當前位置不是0，那么計算就還和以前一樣了。

如果喜歡這篇文章還可以關(guān)注微信公眾號“數(shù)據(jù)結(jié)構(gòu)和算法”，查看更多的算法題

總結(jié)

以上是生活随笔為你收集整理的动态规划立体匹配代码_411，动态规划和递归求不同路径 II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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