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

這題基本上是前一題巴斯卡三角形的孿生題，那題和這題的本質是完全一樣的，只是題目要求稍有不同。

前一題求的是整個巴斯卡三角形，這一題求的是巴斯卡三角形的最後一層。

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

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

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

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

題目敘述

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

巴斯卡三角形的計算過程

巴斯卡三角的計算過程

測試範例

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

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

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

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

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

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

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

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

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

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

例如第二排就是1, 1

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

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

…

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

​last_row = dp( rowIndex-1 )
size = len(last_row)

return [ 1 ] + [ last_row[idx] + last_row[idx+1] for idx in range( size-1) ] + [ 1 ]

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

初始條件呢?

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

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

這裡以Python作為示範

Top down 程式碼

class Solution:
　def getRow(self, rowIndex: int) -> List[int]:
　　
　　if rowIndex == 0:
　　　# Base case
　　　return [1]
　　
　　else:
　　　# General case:
　　　last_row = self.getRow( rowIndex-1 )
　　　size = len(last_row)
　　　return [ 1 ] + [ last_row[idx] + last_row[idx+1] for idx in range( size-1) ] + [ 1 ]

複雜度分析

時間複雜度:O( n^2 )

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

空間複雜度:O( n )

巴斯卡的底為O(n)，DP table剛好和巴斯卡的底一樣大。

學完這題，記得和前面的Pascal Triangle I 做個對照。
基本上是九成像，計算規則也是相同的喔!

前面那題要求的是高度為i的整個巴斯卡三角形。
這題要求的是高度為i的巴斯卡三角形的最後一層。

Reference

[1] Pythonic O( k ) space sol. based on math formula, 90%+ - Pascal's Triangle II - LeetCode

回到DP特訓班目錄 和 學習路徑