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，则不用求和了。