leetcode代码记录(杨辉三角

简介: leetcode代码记录(杨辉三角

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],当然是从第二行开始求解,本位置的值为上面一行里左边和正上方元素的值。把握好遍历的范围即可。

目录
相关文章
|
5月前
力扣-2029-石子游戏-‘屎山’代码
力扣-2029-石子游戏-‘屎山’代码
40 3
|
6月前
|
算法
leetcode代码记录(全排列 II
leetcode代码记录(全排列 II
47 4
|
5月前
|
缓存 算法 数据可视化
LeetCode 题目 119:杨辉三角 II
LeetCode 题目 119:杨辉三角 II
|
5月前
|
存储 SQL 算法
LeetCode 题目 118:杨辉三角
LeetCode 题目 118:杨辉三角
|
6月前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
45 2
|
6月前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
44 2
|
6月前
|
算法
leetcode代码记录(全排列
leetcode代码记录(全排列
48 1
|
6月前
|
索引
leetcode代码记录(Z 字形变换
leetcode代码记录(Z 字形变换
44 1
|
6月前
leetcode代码记录(回文数
leetcode代码记录(回文数
40 1
|
6月前
leetcode代码记录(两数之和
leetcode代码记录(两数之和
37 1