前往
大廳
主題

LeetCode - 64. Minimum Path Sum 解題心得

Not In My Back Yard | 2022-07-09 12:00:13 | 巴幣 2 | 人氣 410

題目連結:


題目意譯:
給定一個大小 m × n 的網格 grid 其中每格填著非負整數。找到一路徑從左上到右下,並使得路徑上所有數字之總和最小化。

注: 你一次只能往下或是往右一格。

限制:
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 200
0 ≦ grid[i][j] ≦ 100



範例測資:
範例 1:
輸入: grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出: 7
解釋: 因為路徑 1 → 3 → 1 → 1 → 1 將總和最小化。

範例 2:
輸入: grid = [[1,2,3],[4,5,6]]
輸出: 12


解題思維:
其實基本就是這題的強化版,或是這題的弱化版。

以後面那題為例,本題沒有需要二分搜的部分,加上每一個格子的數值皆非負,並且本題是要「最小化總和」(該題則是「最大化」)。因此若用該題的符號來描述,則本題的遞迴式將會是
D[i][j] = min(D[i - 1][j], D[i][j - 1]) + grid[i][j]
最後只要看 grid[m][n] 即是所求。




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

創作回應

更多創作