算法题--Pascal三角的生成

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