题目描述
给定一个非负整数
numRows，生成杨辉三角的前numRows行。Try it on Leetcode
输入示例
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
解题思路：动态规划
如果能够知道一行杨辉三角，我们就可以根据每对相邻的值轻松地计算出它的下一行。
算法描述
首先，初始化整个 triangle 列表，三角形的每一行都以子列表的形式存储。
之后，检查行数为 0 的特殊情况，若为 0 则直接返回 []。
如果 numRows > 0，则用 [1] 作为第一行来初始化 triangle，并按如下方式继续填充：
动态规划填充杨辉三角
复杂度分析
- 时间复杂度：$O(numRows^2)$
- 空间复杂度：$O(numRows^2)$
Java 实现
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
// Case 1: if numRows equals zero, then return zero rows.
if (0 == numRows) {
return triangle;
}
// Case 2: the first row is always [1].
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
// Case 3: if numRows > 1, calculate according to the previous row.
for (int curRow = 1; curRow < numRows; curRow++) {
List<Integer> row = new ArrayList<>();
List<Integer> preRow = triangle.get(curRow - 1);
// The first element is 1.
row.add(1);
// DP: row[i][j] = row[i-1][j-1] + row[i-1][j]
for (int j = 1; j < curRow; j++) {
row.add(preRow.get(j-1) + preRow.get(j));
}
// The last element is 1.
row.add(1);
triangle.add(row);
}
return triangle;
}
}
Python 3 实现
class Solution:
def generate(self, num_rows):
triangle = []
for row_num in range(num_rows):
# The first and last row elements are always 1.
row = [None for _ in range(row_num+1)]
row[0], row[-1] = 1, 1
# Each triangle element is equal to the sum of the elements
# above-and-to-the-left and above-and-to-the-right.
for j in range(1, len(row)-1):
row[j] = triangle[row_num-1][j-1] + triangle[row_num-1][j]
triangle.append(row)
return triangle
