10/15 每日一題(巴斯卡三角形 動態規劃)

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

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] 

class Solution:

    def getRow(self, rowIndex: int) -> List[int]:        

        '使用List紀錄之前的計算結果'

        res=[[1],[1,1]]

   

        for i in range(2,rowIndex+1):

            arr=[1]*(i+1) #此時的i是row=i

            for j in range(1,i):

                arr[j]=res[i-1][j-1]+res[i-1][j]

                print(f'arr={arr},res={res},i={i},j={j},row={rowIndex}')

            res.append(arr)

            print(f'新的接成={res}')

       

        return res[rowIndex]

           

--------------------------參考解答

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        tmp = [0] + self.getRow(rowIndex-1) + [0]
        res = []
        for i in range(len(tmp)-1):
            res.append(tmp[i] + tmp[i+1])
        return res