杨辉三角

标签: 数组 动态规划

难度: Easy

给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中,每个数是它左上方和右上方的数的和。

 

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

 

提示:

  • 1 <= numRows <= 30

Submission

运行时间: 15 ms

内存: 15.9 MB

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        if numRows == 1:
            return ans
        for i in range(2, numRows+1):
            row = []
            for j in range(i):
                if j == 0 or j == i - 1:
                    row.append(1)
                else:
                    row.append(ans[i-2][j-1] + ans[i-2][j])
            ans.append(row)
        return ans

Explain

这个题解采用了动态规划的思路。从第二行开始,每一行的数字都等于上一行相邻两个数字之和。具体来说,从第二行开始,每行的第一个和最后一个数字都是1,中间的每个数字等于上一行它左右两个数字之和。在编码实现时,用一个二维列表 ans 来保存结果,其中 ans[i] 表示第 i 行的数字。从第二行开始,每次遍历当前行的每个位置,如果是第一个或最后一个位置,直接添加1;如果是中间位置,将上一行左右两个位置的数字相加得到当前位置的数字。

时间复杂度: O(numRows^2)

空间复杂度: O(numRows^2)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]  # 初始化结果列表,第一行为 [1]
        if numRows == 1:
            return ans  # 如果只有一行,直接返回结果
        for i in range(2, numRows+1):  # 从第二行开始遍历
            row = []  # 当前行的数字
            for j in range(i):  # 遍历当前行的每个位置
                if j == 0 or j == i - 1:  # 如果是第一个或最后一个位置
                    row.append(1)  # 直接添加 1
                else:  # 如果是中间位置
                    row.append(ans[i-2][j-1] + ans[i-2][j])  # 将上一行左右两个位置的数字相加
            ans.append(row)  # 将当前行添加到结果列表中
        return ans  # 返回结果列表

Explore

杨辉三角中,每行的第一个和最后一个数字代表的是组合数学中的组合系数,具体是从n个不同元素中选取0个元素和n个元素的组合方式,这两种情况都只有一种方法,因此这两个位置的数字总是1。

在题解中实现的动态规划方法中不会出现数组访问越界的问题。这是因为代码中已经明确了访问的边界,即只有当索引j在1到i-2之间(即非首尾)时,才会尝试访问上一行的元素。首尾元素直接赋值为1,因此不存在访问上一行不存在的元素的情况。

题解中确实考虑了numRows为1的情况。在代码开始部分,如果numRows的值为1,就直接返回初始化时包含单个元素[1]的列表。这样处理确保了当只需要一行时,程序能够正确返回结果,不会进入后续的行遍历逻辑。