118. 杨辉三角 Pascal's Triangle

题目

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Given an integer numRows, return the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

我的代码

import copy
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:     
        res_list = [[1]]
        if(numRows == 1):return res_list
        else:
            for i in range(1,numRows):
                prev_list = []
                curr_list = []
                prev_list = deepcopy(res_list[-1])
                for j in range(0,len(prev_list)-1):
                    curr_list.append(prev_list[j]+prev_list[j+1])
                curr_list.insert(0,1)
                curr_list.append(1)
                res_list.append(curr_list)
            return res_list

思路

Dynamic Programming

1. 将大问题化成小问题

比如我们要求当前行的list, curr_list，那么我们需要上一行的list，prev_list,
设计转移方法/方程：通过for loop做加法，再收尾插入1 即可得到结果

1. 设置初始值和条件

curr_list = [ ]
prev_list = [ ]
res_list = [[1]], 考虑第一行是特殊情况

1. 考虑特殊情况

第一行长度不足做加法，应当返回[[1]]

细节

python 最烦人的地方就是list a = list b,改变a 也会改变b。所以list的直接赋值经常需要使用深拷贝来区分变量，防止上述错误。

评论区的四行代码法

def generate(numRows):
    pascal = [[1]*(i+1) for i in range(numRows)]
    for i in range(numRows):
        for j in range(1,i):
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
    return pascal

分析

使用了之前学到的list comprehension写法， 因为杨辉三角具有第n行有n个数的特性，每个sublist里的元素数量是固定的，故pascal存储了对应的所有sublist,且每个sublist里元素的值均为1。之后用nested for loop改写需要变动的项。非常简洁的代码哈。

利用map function

def generate(self, numRows):
        res = [[1]]
        for i in range(1, numRows):
            res += [map(lambda x, y: x+y, res[-1] + [0], [0] + res[-1])]
        return res[:numRows]