1. 题目:
给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
2. 我的代码:
class Solution: def generate(self, numRows: int) -> List[List[int]]: # 初始化 result = [[1]] for row in range(1, numRows): result.append([1] + (row - 1) * [0] + [1]) # 递推公式 for row in range(2, numRows): for col in range(1, row): result[row][col] = result[row - 1][col -1] + result[row - 1][col] return result
动态规划,后面的值需要前面的值确定,就像是一个二维的斐波那契数列。首先初始化,把整个三角形的边都初始化为1;然后,递推公式为result[row][col] = result[row - 1][col -1] + result[row - 1][col]
,当然是从第二行开始求解,本位置的值为上面一行里左边和正上方元素的值。把握好遍历的范围即可。