题目：杨辉三角

  • 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
  • 在杨辉三角中，每个数是它左上方和右上方的数的和。

image
image

示例:
输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

来源：力扣（LeetCode）第118题

链接：https://leetcode-cn.com/problems/pascals-triangle

分析：

这题可以使用动态规划，是一道非常简单的题目。我们可以把所要求的值看成是前一行的两个值的相加，而且这两个值的位置是有规律的。

思路：

  • 两个循环，第一遍遍历所有的层。
  • 第二遍遍历每一层中的值。
  • 每一层中的值只有第一个和最后一个是1，其他的值都是前一行的前一个位置和现在的位置的和。

代码：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        for i in range(numRows):
            numRow = [1 for _ in range(i + 1)]
            for j in range(1, i):
                numRow[j] = ans[i-1][j-1] + ans[i-1][j]
            ans.append(numRow)
        return ans

复杂度分析：

  • 时间复杂度：O(n^2^) n 为numRows
  • 空间复杂度：O(n^2^)