118. 杨辉三角

Difficulty
easy
Tags
动态规划
URL
https://leetcode-cn.com/problems/pascals-triangle/
Star
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
notion imagenotion image
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
  • 1 <= numRows <= 30
通过次数243,367提交次数330,383

法1 动态规划

思路
每一层都有上一层计算出来的。
题解
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 1:
            return [[1]]
        res = [[1]]
        for i in range(1, numRows):
            temp = [1] # 每一行开头有一个1
            for j in range(0,i-1):
                temp.append(res[i-1][j]+res[i-1][j+1])
            temp.append(1) # 每一行结尾有一个1
            res.append(temp[:])
        
        return res