LeetCode 118 Pascal's Triangle

LeetCode

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:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

* 1 <= numRows <= 30

题目大意：

给定n行，产生n行的杨辉三角

解题思路：

用DP按照定义生成，其实类似于Fibonacci数列，不过是二维的，而不是一维。

解题步骤：

N/A

注意事项：

初始值为[1]

Python代码：

def generate(self, numRows: int) -> List[List[int]]:
	path, res = [1], []
	res.append(path)
	for i in range(1, numRows):
		next_level = []
		for j in range(1, len(path)):
			next_level.append(path[j - 1] + path[j])
		next_level.insert(0, 1)
		next_level.append(1)
		path = next_level
		res.append(list(path))
	return res

算法分析：

时间复杂度为O(numRows²)，空间复杂度O(1)