LeetCode--杨辉三角

题干：

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

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

示例:

class Solution {public List> generate(int numRows) {List> dataList = new ArrayList>();if(numRows == 0){return dataList;}for(int i=1;i<=numRows;i++){List list = new ArrayList();for(int j=1;j<=i;j++){list.add(num(i,j));}dataList.add(list);}return dataList;}public static int num(int x,int y){if(y==1||y==x){return 1;}int c=num(x-1,y-1)+num(x-1,y);return c;}
}

解答二（LeetCode官方）：

方法：动态规划

思路

如果能够知道一行杨辉三角，我们就可以根据每对相邻的值轻松地计算出它的下一行。

算法

虽然这一算法非常简单，但用于构造杨辉三角的迭代方法可以归类为动态规划，因为我们需要基于前一行来构造每一行。

首先，我们会生成整个 triangle 列表，三角形的每一行都以子列表的形式存储。然后，我们会检查行数为 00 的特殊情况，否则我们会返回 [1][1]。如果 numRows > 0numRows>0，那么我们用 [1][1] 作为第一行来初始化 triangle with [1][1]，并按如下方式继续填充

class Solution {public List> generate(int numRows) {List> triangle = new ArrayList>();// First base case; if user requests zero rows, they get zero rows.if (numRows == 0) {return triangle;}// Second base case; first row is always [1].triangle.add(new ArrayList<>());triangle.get(0).add(1);for (int rowNum = 1; rowNum < numRows; rowNum++) {List row = new ArrayList<>();List prevRow = triangle.get(rowNum-1);// The first row element is always 1.row.add(1);// Each triangle element (other than the first and last of each row)// is equal to the sum of the elements above-and-to-the-left and// above-and-to-the-right.for (int j = 1; j < rowNum; j++) {row.add(prevRow.get(j-1) + prevRow.get(j));}// The last row element is always 1.row.add(1);triangle.add(row);}return triangle;}
}

复杂度分析

• 时间复杂度：O(numRows^2)O(numRows2)

  虽然更新 triangle 中的每个值都是在常量时间内发生的， 但它会被执行 O(numRows^2)O(numRows2) 次。想要了解原因，就需要考虑总共有多少 次循环迭代。很明显外层循环需要运行 numRowsnumRows 次，但在外层循环的每次迭代中，内层 循环要运行 rowNumrowNum 次。因此，triangle 发生的更新总数为 1 + 2 + 3 + \ldots + numRows1+2+3+…+numRows，根据高斯公式 有

  \begin{aligned} \frac{numRows(numRows+1)}{2} &= \frac{numRows^2 + numRows}{2} \\ &= \frac{numRows^2}{2} + \frac{numRows}{2} \\ &= O(numRows^2) \end{aligned}2numRows(numRows+1)​​=2numRows2+numRows​=2numRows2​+2numRows​=O(numRows2)​

• 空间复杂度：O(numRows^2)O(numRows2)

  因为我们需要存储我们在 triangle 中更新的每个数字， 所以空间需求与时间复杂度相同。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！