主題

LeetCode - 63. Unique Paths II 解題心得

Not In My Back Yard | 2021-05-12 00:00:01 | 巴幣 0 | 人氣 261

題目連結:


題目意譯:
一個機器人位於一個 m × n 網格的左上角(在下面的圖裡標註為 "Start")。

機器人在任意時間點只能往下或往右移動。機器人試圖抵達網格的右下角(在下面的圖裡標註為 "Finish")。

現在有一些障礙物被加入到網格裡。試問有多少相異路徑存在?

一個障礙物以及一個空地分別被標註為網格中的 1 和 0。

限制:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 ≦ m 、 n ≦ 100
obstacleGrid[i][j] 為 0 或是 1。



範例測資:
範例 1:
輸入: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出: 2
解釋: 上面的 3 × 3 網格中有一個障礙物位於中心。
有兩個方式可以抵達右下角:
1. 右 → 右 → 下 → 下
2. 下 → 下 → 右 → 右

範例 2:
輸入: obstacleGrid = [[0,1],[0,0]]
輸出: 1


解題思維:
類似昨天的題目之論述。只是本題中所有有障礙物(假設位於(i, j))的位置之 D[i][j] 值必為 0。而遞迴式基本上沒變,所以一樣可以從左上角算到右下角,得到 D[m][n] 之值,即所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作