變形「最小路徑和」問題 & 常見 DP 空間最佳化技巧

題目描述

這是 LeetCode 上的

120. 三角形最小路徑和

，難度為 Medium。

給定一個三角形 triangle ，找出自頂向下的最小路徑和。

每一步只能移動到下一行中相鄰的結點上。

相鄰的結點在這裡指的是下標與上一層結點下標相同或者等於上一層結點下標 + 1 的兩個結點。

也就是說，如果正位於當前行的下標 i ，那麼下一步可以移動到下一行的下標 i 或 i + 1 。

示例 1：

輸入：triangle = ［［2］，［3，4］，［6，5，7］，［4，1，8，3］］輸出：11解釋：如下面簡圖所示： 2 3 4 6 5 74 1 8 3自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

輸入：triangle = ［［-10］］輸出：-10

提示：

1 <= triangle。length <= 200

triangle［0］。length == 1

triangle［i］。length == triangle［i - 1］。length + 1

−104-10^4−104 <= triangle［i］［j］ <= 10410^4104

進階：

你可以只使用 O（n）O（n）O（n）的額外空間（n 為三角形的總行數）來解決這個問題嗎？

動態規劃解法

對於此類（具有形狀的）題目，如果並不熟練，我的建議是先畫出真實的陣列分佈情況。

以樣例一的資料為例，真實的 triangle 分佈應該是：

23 46 5 74 1 8 3

先把圖畫出來，之後我們再來分析，這道題我們是如何想到 DP 的。

如何確定一道題目是否可以用 DP 解決，我們要從

有無後效性

進行分析。

首先，既然是從上到下的路徑，那麼最後一個點必然是落在最後一行。

對於最後一行的某個位置的值，根據題意只能從上一行的

某一個位置

或者

某兩個位置之一

轉移而來。

同時，我們只關注前一位的累加值是多少，而不關心這個累加值結果是由什麼路徑而來的。

這顯然就滿足了「無後效性」的定義：我們轉移某個狀態需要用到某個值，但是並不關心該值是如何而來的。

更加的學術表達是：當前某個狀態確定後，之後的狀態轉移與之前的決策無關

因此我們可以確定使用 DP 進行求解。

接下來的問題是，我們該如何確定狀態定義呢？

通常我們會根據結尾和答案來猜 DP 的狀態定義。

所謂的結尾通常就是指最後一步。

對於本題，我們結合兩者可以猜一個 DP 狀態： f［i］［j］代表到達某個點的最小路徑和。

那麼 min（f［n−1］［i］）min（f［n-1］［i］）min（f［n−1］［i］）（最後一行的每列的路徑和的最小值）就是答案。

再結合我們剛剛畫的分佈圖：

23 46 5 74 1 8 3

透過觀察可以發現以下性質（令i為行座標，j為列座標）：

每一行 i 具有 i+1 個數字

只要不是第一列（j！=0）位置上的數，都能透過

左上方

轉移過來

只要不是每行最後一列（j！=i）位置上的數，都能透過

上方

轉移而來

同時，這樣的分析/轉移過程，是可以推廣並覆蓋所有位置的。

至此，整個過程都沒有問題，狀態轉移方程也能不重不漏的列舉到每一條路徑。

因此這個 DP 狀態定義可用。

PS。由於題目的「進階」部分要求我們使用 O（n）O（n）O（n）空間複雜度。那麼三葉先寫個 O（n2）O（n^2）O（n2）解法好了。

程式碼：

class Solution { public int minimumTotal（List> tri） { int n = tri。size（）； int ans = Integer。MAX_VALUE； int［］［］ f = new int［n］［n］； f［0］［0］ = tri。get（0）。get（0）； for （int i = 1； i < n； i++） { for （int j = 0； j < i + 1； j++） { int val = tri。get（i）。get（j）； f［i］［j］ = Integer。MAX_VALUE； if （j ！= 0） f［i］［j］ = Math。min（f［i］［j］， f［i - 1］［j - 1］ + val）； if （j ！= i） f［i］［j］ = Math。min（f［i］［j］， f［i - 1］［j］ + val）； } } for （int i = 0； i < n； i++） ans = Math。min（ans， f［n - 1］［i］）； return ans； }}

時間複雜度：O（n2）O（n^2）O（n2）

空間複雜度：O（n2）O（n^2）O（n2）

進階

從我們遞推過程可以發現，在求第 i 行的狀態時只依賴於第 i-1 行的狀態。

那麼我們不需要儲存所有行的狀態值（動規值），可以對空間進行最佳化。

通常 DP 的空間最佳化思路有兩種：

滾動陣列

根據狀態依賴調整迭代/迴圈的方向

其中滾動陣列的最佳化方式，是我最推薦的。

因為沒有任何的思維難度，只需要將其中一維直接改成 2，任何在將維的 f［i］改成 f［i&1］或者 f［i%2］即可（推薦前者，在不同架構的機器上，運算效率更加穩定）。

class Solution { public int minimumTotal（List> tri） { int n = tri。size（）； int ans = Integer。MAX_VALUE； int［］［］ f = new int［2］［n］； f［0］［0］ = tri。get（0）。get（0）； for （int i = 1； i < n； i++） { for （int j = 0； j < i + 1； j++） { int val = tri。get（i）。get（j）； f［i & 1］［j］ = Integer。MAX_VALUE； if （j ！= 0） f［i & 1］［j］ = Math。min（f［i & 1］［j］， f［（i - 1） & 1］［j - 1］ + val）； if （j ！= i） f［i & 1］［j］ = Math。min（f［i & 1］［j］， f［（i - 1） & 1］［j］ + val）； } } for （int i = 0； i < n； i++） ans = Math。min（ans， f［（n - 1） & 1］［i］）； return ans； }}

事實上，這道題的空間還可以最佳化到 O（1）O（1）O（1）：利用輸入資料的空間進行狀態轉移。

這部分的編碼實現不難，就當是我給你留的作業吧 ~

總結

這是一道毫無疑問的「DP 裸題」，但我仍然希望你去摳我題解寫的每一步思考過程。

想想我們以前是怎麼學數學的，每個知識點必然是用很簡單的模板題來教學的。

只有這樣我們才能學會這個知識點，才能學到知識點裡的精髓，而不是被細節衝昏頭腦。

對於這道題的「完整思考」過程，我們應該做到每一步都是「有理有據」，由邏輯推導而來。

而這些分析技巧我都在路徑問題第一講跟你講過。

而且隨著動態規劃系列的進行，我們還會不斷強化這些分析方法。

此外，我還給你介紹了常規的 DP 空間手段，希望你能加深理解 ~

在這道題上空間最佳化是可選的（不最佳化空間也能 AC），但在某些題下則是必須的。

作者：宮水三葉的刷題日記