image.png
0. 链接
1. 题目
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
image.png
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
2. 思路1: 动态规划
- 时间复杂度:
O(N^2) - 空间复杂度:
O(N^2)
3. 代码
# coding:utf8
from typing import List
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
rtn_list = list()
if numRows == 0:
return rtn_list
rtn_list.append([1])
for i in range(1, numRows):
last_list = rtn_list[-1]
each_list = list()
each_list.append(last_list[0])
for j in range(1, len(last_list)):
each_list.append(last_list[j - 1] + last_list[j])
each_list.append(last_list[-1])
rtn_list.append(each_list.copy())
return rtn_list
solution = Solution()
print('input: {}, output: {}'.format(5, solution.generate(5)))
输出结果
input: 5, output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
4. 结果
image.png
