不同路徑 II

題目描述：一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。

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

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

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/unique-paths-ii/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸法

首先，經(jīng)過分析可知，到達任意一個單元格子的最后一步，可以從這個格子的左邊過來，也可以從這個格子的上邊過來，所以到達任意一個格子的步數(shù)是到它左邊的步數(shù)加上到它上面格子的步數(shù)之和，所以可以用遞歸的方法求解，具體過程如下：

• 如果m等于1或者n等于1，直接返回1；

• 如果上面的條件不滿足，則遞歸調(diào)用該方法求解uniquePaths(m - 1, n) + uniquePaths(m, n - 1)。

說明：和LeetCode-062-不同路徑的區(qū)別在于，當(dāng)左邊或者上面的走法為0（即走不通的時候），則只用繼續(xù)往一個方向遞歸。

解法二：迭代法

首先記錄第一行的格子的走法columns，從第一個元素開始判斷，如果第一個元素的值為1（即有障礙物），則為0，然后給columns的后面的元素賦值，賦值時需要同時判斷前面一個元素的值和當(dāng)前位置是否有障礙物。然后根據(jù)columns迭代獲取下面每一行相應(yīng)的走法，迭代過程如下：

• 首先根據(jù)上一行第一個元素的值和當(dāng)前行第一個元素是否有障礙物獲取columns[0]的值；

• 然后重復(fù)上面的過程，給columns的后面的元素賦值，賦值時需要同時判斷前面一個元素的值和當(dāng)前位置是否有障礙物。

最后返回columns最后一個元素的值即為最終的走法。

說明：解決過程類似 LeetCode-062-不同路徑，特別注意當(dāng)?shù)谝粋€元素為1時，則走不通；當(dāng)只有一個元素時，且為0時，返回1也就是有一種走法，而不是返回0。

【每日寄語】 機會不會等你，錯過以后可能不會再有。