118. 杨辉三角
一句话套路tri[i][j]=上一行相邻两数之和
题目描述
给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。

示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
提示:
1 <= numRows <= 30
思路
时间
O(n^2)空间
O(n^2)(输出本身)状态
tri[i][j] = tri[i-1][j-1] + tri[i-1][j],边界每行首尾为 1。
变体
Q119 只返回第 rowIndex 行 -> 逆序原地滚动成一行,空间 O(k);
另一个视角
第 n 行第 k 个数就是组合数 C(n, k)。
图解
第 k 行第 j 个数 = C(k,j)。从上一行递推即可。
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0118 {
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> tri(numRows);
for (int i = 0; i < numRows; ++i) {
tri[i].assign(i + 1, 1); // 每行首尾都是 1
for (int j = 1; j < i; ++j) tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
}
return tri;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0118::Solution s;
CHECK_EQ(s.generate(5),
vector<vector<int>>({{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 6, 4, 1}}));
CHECK_EQ(s.generate(1), vector<vector<int>>({{1}}));
CHECK_EQ(s.generate(3)[2], vector<int>({1, 2, 1}));