非主营电子商务企业网站有哪些/东营百度推广公司

一、题目描述

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

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

 示例:

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

二、解题思路

杨辉三角具有以下性质：

1、每行数字左右对称，由 1 开始逐渐变大再变小，并最终回到 1。
2、每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 n 行的第 i 个数等于第 n−1 行的第 i-1个数和第 i 个数之和。

依据性质 2，我们可以一行一行地计算杨辉三角。每当我们计算出第 i 行的值，我们就可以使用动态规划的思想在线性时间复杂度内计算出第i+1 行的值。

首先我们构造整个三角形列表，三角形的每一行以子列表的形式存储。

然后我们会检查行数为0的特殊情况，否则我们返回[1]。

如果numRows>0，我们会用[1]来作为第一行来初始化三角形列表，并按照如下方式填充

1

1，1

1，2，1

1，3，3，1

1，4，6，4，1

动态转移方程为a[i][j]=a[i-1