主題

LeetCode - 62. Unique Paths 解題心得

Not In My Back Yard | 2021-05-11 00:00:03 | 巴幣 0 | 人氣 27

題目連結:


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

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

試問有多少可能的相異路徑存在著?

限制:
1 ≦ m 、 n ≦ 100
保證答案值小於等於 2 × 10 ^ 9。



範例測資:
範例 1:
輸入: m = 3, n = 7
輸出: 28

範例 2:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角,有 3 條路徑可以抵達右下角:
1. 右 → 下 → 下
2. 下 → 下 → 右
3. 下 → 右 → 下

範例 3:
輸入: m = 7, n = 3
輸出: 28

範例 4:
輸入: m = 3, n = 3
輸出: 6


解題思維:
令 D[i][j] 為從起點 (1, 1) 走到 (i, j) 之方法數。因此所求為 D[m][n]。

已知對於任意 i 、 j 值, D[i][1] 和 D[1][j] 之值皆為 1 (因為只有一條路可以走)。而每次機器人只能從某個位置往下或往右走,因此 D[i][j] (i > 1 且 j > 1)之值等於
D[i - 1][j] + D[i][j - 1]

根據上列遞迴式以及初始條件,我們便可從左上角 (1, 1) 一路推到右下角 (m, n)。而此時便可以知道 D[m][n] 之值,即所求。




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

創作回應

更多創作