主題

LeetCode - 120. Triangle 解題心得

Not In My Back Yard | 2021-04-29 00:00:14 | 巴幣 0 | 人氣 53

題目連結:


題目意譯:
給定一個陣列 triangle,回傳從頂部到底部的最小路徑和。

對於每一步,你可以移動到下一列的相鄰數字。更正式地,如果你位於當前列的索引值 i 之位置,你可以移動到下一列的索引值 i 或是 i + 1 之位置。

限制:
1 ≦ triangle.length ≦ 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10 ^ 4 ≦ triangle[i][j] ≦ 10 ^ 4
 
進階: 你可以完成此題藉由 O(n) 的額外空間嗎?其中 n 為陣列 triangle 的列數。



範例測資:
範例 1:
輸入: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出: 11
解釋: triangle 看起來像是以下:
   2
  3 4
6 5 7
4 1 8 3
從頂到底的最小路徑和為 2 + 3 + 5 + 1 = 11 (如上之底線所標示數字)

範例 2:
輸入: triangle = [[-10]]
輸出: -10


解題思維:
定義 D[i][j] 為走到第 i 列第 j 個位置的最小路徑和。

根據題意,我們可以得到遞迴式
D[i][j] = min(D[i - 1][j - 1], D[i - 1][j]) + triangle[i][j]
且觀察後可得初始條件
D[0][0] = triangle[0][0]

因此,我們可以從第 1 列開始推得所有索引值 j 的 D[1][j] ,進而推得第 2 列的所有位置 j 的 D[2][j]……以此類推。

而最後我們只須看哪個位置 j 的 D[n - 1][j] 之值(n 為 triangle 之列數)最小,即是所求。



至於如果要將空間複雜度變為 O(n),可以藉由交錯使用兩個長度為 n 之陣列。例如計算 D[2][j] 使用第一個陣列、D[3][j] 使用第二個、D[4][j] 回頭使用第一個等等。這樣便不需要開滿 n 個長度為 n 的陣列,使得空間複雜度為 O(n ^ 2) 了。




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

創作回應

更多創作