DP動態規劃 深入淺出 以Pascal Triangle 巴斯卡三角形 為例

今天再來看一題入門的2D DP題目: 巴斯卡三角形

詳細的題目可在這裡看到

再次複習Dynamic programming的解題框架，可分為三大步驟

1.定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

題目給定高度n，要求我們造出並且輸出高度為n的巴斯卡三角形

巴斯卡三角的計算過程

範例輸入輸出如下:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

好，接著一起走過解題框架的三大步驟

1. 定義狀態 [我在哪裡]

我們可以定義DP[i] = 高度為i的巴斯卡三角形

那麼最終DP[n]就是我們的解答，也是最後輸出結果。

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

這題沒給，但我們可以根據題目的規定進行推導

這裡把官方網站給的動畫再貼一次，幫助大家觀察其規律

上一排的左右兩項相加=下一層這一項的值

我們可以發現，下一排的生成就是

頭部的1, 上一排去掉頭尾的內部元素兩兩相加 , 尾巴的1

例如第二排就是1, 1

第三排就是1, (1+1) , 1

第四排則是1, (1+2), (2+1), 1

…

依此類推，用python風格虛擬碼來表示，如下方所示

prevPascal = dp(level-1)

cur_row =  [ [1] + [ (prevPascal[-1][i] + prevPascal[-1][i+1]) for i in range(level-2) ] +[1] ]

return prevPascal + cur_row​

3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]

初始條件呢?

在這題很明顯，就是高度為一的巴斯卡三角，也就是[ [1] ]

到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，

這裡以Python作為示範

Top-dowm程式碼:

class Solution:
　def generate(self, numRows: int) -> List[List[int]]:
　　
　　def dp( level ):
　　　
　　　if level == 1:
　　　　# base case:
　　　　return [ [1] ]

　　　else:
　　　　# general cases:
　　　　prevPascal = dp(level-1)
　　　　
　　　　cur_row =  [ [1] + [ (prevPascal[-1][i] + prevPascal[-1][i+1]) for i in range(level-2) ] +[1] ]
　　　　
　　　　return prevPascal + cur_row

　　
　　# -----------------------------------------------------------------------------------
　　return dp(level=numRows)

時間複雜度:

O( n^2 )
巴斯卡的三角形高度為O(n)，底也為O(n)，對應遞迴呼叫深度與每一層遞迴的計算成本。

空間複雜度:

O( n^2 )
巴斯卡的三角形高度為O(n)，底也為O(n)，DP table剛好和巴斯卡三角形一樣大。

Bottom-up程式碼:

class Solution:
　def generate(self, numRows: int) -> List[List[int]]:
　　
　　
　　pascal_tri = []
　　
　　# build each row
　　for i in range( numRows ):
　　　　　　　
　　　cur_row = [ 1 ] * (i+1)
　　　
　　　# update each element on current row i
　　　for j in range( len(cur_row) ):
　　　　
　　　　if j != 0 and j != i:
　　　　　cur_row[j] = pascal_tri[i-1][j-1] + pascal_tri[i-1][j]
　　　　　
　　　pascal_tri.append( cur_row )
　　　
　　return pascal_tri

O( n^2 )
巴斯卡的三角形高度為O(n)，底也為O(n)，對應雙層迴圈內部的計算成本。

空間複雜度:

O( n^2 )
巴斯卡的三角形高度為O(n)，底也為O(n)，DP table剛好和巴斯卡三角形一樣大。

Reference:

[1] Python/JS O( n^2 ) DP [w/ Comment] - Pascal's Triangle - LeetCode