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: 動(dòng)態(tài)規(guī)劃
- 時(shí)間復(fù)雜度:
O(N^2) - 空間復(fù)雜度:
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)))
輸出結(jié)果
input: 5, output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
4. 結(jié)果
image.png
