算法题--Pascal三角第K行的生成

image.png

0. 链接

题目链接

1. 题目

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

image.png

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

2. 思路1: 动态规划

• 时间复杂度: O(K^2)
• 空间复杂度: O(K)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def generate(self, rowIndex: int) -> List[List[int]]:
        rtn_list = list()
        if rowIndex == 0:
            return rtn_list
        rtn_list.append(1)
        for i in range(1, rowIndex + 1):
            pre_zero_list = [0] + rtn_list
            after_zero_list = rtn_list + [0]
            rtn_list.append(0)
            for j in range(len(rtn_list)):
                rtn_list[j] = pre_zero_list[j] + after_zero_list[j]
        return rtn_list


solution = Solution()
print('input: {}; output: {}'.format(3, solution.generate(3)))

输出结果

input: 3; output: [1, 3, 3, 1]

4. 结果

image.png