杨辉三角
给定一个非负整数 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
动态规划-逐行构造：
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans(numRows);
for (int i = 0; i < numRows; i++)
{
ans[i].resize(i + 1);
ans[i][0] = 1;
ans[i][i] = 1;
for (int j = 1; j < i; j++)
{
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
}
return ans;
}
};
核心思想
杨辉三角的每一行都可以由上一行推出来。
观察前几行：
第 0 行： [1]
第 1 行： [1,1]
第 2 行： [1,2,1]
第 3 行： [1,3,3,1]
第 4 行： [1,4,6,4,1]
可以发现两个规律：
- 每一行的第一个数和最后一个数都是
1。 - 中间的每个数，等于上一行左上方和右上方两个数之和。
所以我们只需要从第 0 行开始，一行一行往下构造。
状态定义
令：
ans[i][j]
表示杨辉三角中第 i 行第 j 列的数字。
这里使用的是从 0 开始的下标。
所以：
- 第
0行有1个数 - 第
1行有2个数 - 第
2行有3个数 - 第
i行有i + 1个数
因此代码中每一行都要先设置长度：
ans[i].resize(i + 1);
递推公式推导
对于第 i 行第 j 列的数字，需要分两种情况。
1. 边界位置
如果 j == 0，说明它是这一行最左边的数字。
如果 j == i，说明它是这一行最右边的数字。
杨辉三角两侧边界都固定为 1。
所以：
ans[i][0] = 1
ans[i][i] = 1
代码中对应：
ans[i][0] = 1;
ans[i][i] = 1;
2. 中间位置
如果当前位置不是边界，也就是：
1 <= j <= i - 1
那么它由上一行两个相邻位置相加得到：
- 左上方：
ans[i - 1][j - 1] - 右上方：
ans[i - 1][j]
所以递推公式是：
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]
代码中对应：
for (int j = 1; j < i; j++)
{
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
为什么可以从上到下构造
计算第 i 行时，只会用到第 i - 1 行。
也就是说：
ans[i][j]
只依赖：
ans[i - 1][j - 1]
和：
ans[i - 1][j]
所以只要我们按照行号从小到大构造，就能保证在计算当前行时，上一行已经全部算好了。
这就是动态规划的顺序。
正确性证明
我们证明算法生成的 ans 正好是杨辉三角的前 numRows 行。
归纳基
当 i = 0 时，第 0 行只有一个数字。
代码执行：
ans[0][0] = 1;
所以第 0 行为：
[1]
这与杨辉三角定义一致。
归纳假设
假设第 0 行到第 i - 1 行都已经被正确构造。
也就是说，上一行 ans[i - 1] 中的每个数字都是正确的。
归纳推导
现在构造第 i 行。
对于左右两个边界位置：
j = 0
和：
j = i
代码都赋值为 1，这符合杨辉三角两侧边界为 1 的定义。
对于中间位置：
1 <= j <= i - 1
代码使用：
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]
根据归纳假设，上一行的 ans[i - 1][j - 1] 和 ans[i - 1][j] 都是正确的。
而杨辉三角的定义正是“每个中间数等于它左上方和右上方的数之和”。
所以第 i 行的每一个位置都被正确构造。
由数学归纳法可知，算法生成的所有行都正确。
举例理解
以 numRows = 5 为例。
构造过程如下：
- 第
0行：[1] - 第
1行：两边都是1，得到[1,1] - 第
2行：中间值是1 + 1 = 2，得到[1,2,1] - 第
3行：中间值分别是1 + 2 = 3、2 + 1 = 3，得到[1,3,3,1] - 第
4行：中间值分别是1 + 3 = 4、3 + 3 = 6、3 + 1 = 4，得到[1,4,6,4,1]
最终返回：
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
复杂度分析
第 i 行有 i + 1 个数字。
所以总共需要生成的数字个数是：
1 + 2 + 3 + ... + numRows
根据等差数列求和：
1 + 2 + ... + numRows = numRows * (numRows + 1) / 2
因此时间复杂度是：
O(numRows^2)
返回结果本身也需要存储这些数字，所以空间复杂度是：
O(numRows^2)
这里的空间主要是输出数组所占空间。