[從leetcode學演算法 - Dynamic programming] 第一篇 - 119. Pascal's Triangle II (使用python 撰寫)－國全張的部落格

很久沒更新 QQ，最近想持續寫leetcode 磨練自己演算法技巧

先來練練leetcode裡面歸類為easy 的 Pascal's Triangle II ，

1. 題目網址：

https://leetcode.com/problems/pascals-triangle-ii/description/

2. 題目敘述:

[從leetcode學演算法 - Dynamic progr

如上圖，給定rowIndex，回傳該排rowIndex的所有數字，比如輸入 3，輸出 [1,3,3,1]，輸入4，輸出 [1,4,6,4,1]

3. 解題想法:

先來用一些符號作名詞解釋，

rowIndex 為1，我們寫成 A1，然後 A1 = [1]

rowIndex為2，我們寫成 A2，然後 A2 = [1, 1]

rowIndex為3，我們寫成 A3，然後 A3 = [1,3,3,1]

思考以上rowIndex為3，用以上定義的符號，也就是A3， A3 = [1,3,3,1]，我們來拆解[1,3,3,1]中每個數字是怎麼來的，

這裡把 A3的[1,3,3,1] 寫成直的，並分析他是怎麼來的：

數字	由來	說明
1	A3[0] = A2[0]	第三排的第0個數字，等於第二排的第0個數字
3	A3[1] = A2[0] + A2[1]	第三排的第1個數字，等於第二排的第0個數字加第二排的第1個數字
3	A3[2] = A2[1] + A2[2]	第三排的第0個數字，等於第二排的第0個數字加第二排的第2個數字
1	A3[3] = A2[2] + A2[3]	第三排的第0個數字，等於第二排的第2個數字

換個方式說，由上四個數字可知:

第一數字 1是 A3-1[1-1]

第二數字 3是 A3-1[1-1] + An[1]

第三數字3是 A3-1[2-1] + An[2]

第四數字1是 A3-1[3-1] + An[3]

這裡再加上i表示index，我們把它寫成更通用的公式

1. i=0 or i=last index: 回傳 1 (第0個元素或最後一個元素，數值都是1， ex: A3[0] = 1, A3[3] = 1 )

2. i= other index ，回傳 An-1[i-1] + An-1[i] (其他index，An可以寫成前面這個公式，ex: A3[1] = A2[0] + A2[1]， A3[2] = A2[1] + A2[2])

如果你看得懂以上的關係式，就可以來寫程式了:

因為程式限制n最大是33，不會有maximum recursion depth exceeded的問題

class Solution:
saved = [[1], [1,1]] # 定義第一層與第二層
 
def getRow(self, rowIndex: int):
try: 
return self.saved[rowIndex] # 如果有該陣列就返回該陣列
except:
prev_saved = self.getRow(rowIndex-1) # 如果沒有該陣列就遞迴去計算出該陣列
# first must be 1
  new_list = [1] 
# other index is An = An-1[i-1] + An-1[i] 
for i in range(1, len(prev_saved)):
new_list.append((prev_saved[i-1] + prev_saved[i]))
 
# last must be 1
new_list.append(1)
self.saved.append(new_list)
return new_list