LeetCode 118 Pascal's Triangle

LeetCode

<div>

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:

<pre>Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] </pre>

Example 2:

<pre>Input: numRows = 1 Output: [[1]] </pre>

Constraints:

• 1 <= numRows <= 30

</div>

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

1. 初始值为[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

算法分析：

时间复杂度为<code>O(numRows²)</code>，空间复杂度O(1)