2.6 金字塔最小路徑之和 ????? 題目描述: 給定一個金字塔形狀的二維數(shù)組，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結(jié)點(diǎn)上。例如，給定如下二維數(shù)組： ``` [ ?[2], ?[3, 4], ?[6, 5, 7], ?[4, 1, 8, 3] ] ``` 自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。注意：如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個問題，那么你的算法會很加分。 題目解析: 解法一：二維動態(tài)規(guī)劃 ?? 金字塔為： ``` [2], [3, 4], [6, 5, 7], [4, 1, 8, 3] ``` 反過來直接往上加： ```python dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + triangle[i][j] ``` 這個式子的大致意思是，選擇上一層的兩個相鄰節(jié)點(diǎn)中和較小的那個，再加上當(dāng)前節(jié)點(diǎn)的值。這是一個經(jīng)典的動態(tài)規(guī)劃問題。 解法二：一維動態(tài)規(guī)劃 ?? 同樣是動態(tài)規(guī)劃，我們可以將問題稍微優(yōu)化，把每一行的數(shù)列都左對齊，如下： ``` [ ?[2], ?[3, 4], ?[6, 5, 7], ?[4, 1, 8, 3] ] ``` 可以看出來，實際上從上一行到下一行只有兩個選擇，橫坐標(biāo)不變或加一。我們可以使用一個一維數(shù)組 dp[j] 表示從底層到當(dāng)前層的第 j 個元素所有路徑中最小的和。遞推關(guān)系就是： ```python dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]) ``` 即下一行與它相鄰的兩個節(jié)點(diǎn)中和較小的再加上它自己的值。這樣在一維空間內(nèi)完成了 dp，符合題目挑戰(zhàn)。 這個解法的 dp 數(shù)組變化如下： ``` [4, 1, 8, 3] [7, 6, 10, 3] ... ``` 參考代碼: ```python class Solution(object): ??def minimumTotal(self, triangle): ????n = len(triangle) ????dp = triangle[-1] ????for i in range(n - 2, -1, -1): ??????for j in range(i + 1): ????????dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]) ????return dp[0] ``` 這兩種動態(tài)規(guī)劃的方法都可以有效地解決問題，選擇適合你的方式進(jìn)行實現(xiàn)。 ???? 希望這些方法能幫助你更專業(yè)地解決金字塔最小路徑和問題！如果有任何疑問或需要進(jìn)一步的解釋，請隨時提出。 ???????