leetcode python3 簡單題118. Pascal's Triangle

1.編輯器

我使用的是win10+vscode+leetcode+python3

環境配置參見我的部落格：

連結

2.第一百一十八題

（1）題目

英文：

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

中文：

給定一個非負整數 numRows，生成楊輝三角的前 numRows 行。

在楊輝三角中，每個數是它左上方和右上方的數的和。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/pascals-triangle

（2）解法

① 遞歸法

（耗時：44ms，記憶體：13.7M）

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]
        upper = self.generate(numRows - 1)
        upper.append([1] + [upper[-1][i-1] + upper[-1][i] for i in range(1, numRows-1)] + [1])
        return upper
           

② 動态規劃法

（耗時：32ms，記憶體：13.6M）

class Solution:
    def generate(self, numRows):
        if numRows <= 0: return []
        triangle = []
        for row in range(numRows):
            if row == 0:
                triangle.append([1])
            else:
                tmp = [1]
                for c in range(row):
                    sum = (triangle[row-1][c] + 0) if (c == row-1) else (triangle[row-1][c]+triangle[row-1][c+1])
                    tmp.append(sum)
                triangle.append(tmp)
        return triangle
           

注意：

1.

if (c == row-1)

這個是用來判斷是否到了

triangle[row-1]

中的最後一個元素，如果是True，則不用求和了。