边界恒为 1，内部由上一行相邻两数相加，逐行递推生成。
OJ: leetcodecn
题目 ID: pascals-triangle
难度:入门
标签:动态规划递推
创建: 2026-07-29 12:35
更新: 2026-07-29 15:20
后置题目
roj 3562传球游戏B 的 DP 逐层计数直接沿用了 A 教的「本层每格 = 上一层两个相邻格子相加」这一步二维逐层递推，只把上一层下标加取模改成左右邻居并补了边界与环的处理roj 1258【例9.2】数字金字塔数字金字塔把杨辉三角「由相邻两数相加得下一格」的二维递推骨架换成相邻两数取 max 再累加自身，逐层递推思路直接迁移，只是多了求最大值的取优步骤luogu P1057[NOIP 2008 普及组] 传球游戏A 教的 `ans[i][j]=ans[i-1][j-1]+ans[i-1][j]` 这种「上一层相邻两项相加」的填表递推，被 B 直接用作 `dp[i][j]=dp[i-1][left(j)]+dp[i-1][right(j)]` 的状态转移，只在相邻位置上加了环形边界处理。luogu P1002[NOIP 2002 普及组] 过河卒A 教的「相邻两格数值相加、逐行填表并给边界置 1」被 B 的网格路径计数沿用：dp[x][y]=dp[x-1][y]+dp[x][y-1] 就是把左/上两个相邻格当作两个前驱相加，起点同样置 1。
题意
生成杨辉三角的前 n 行。
思路
每行边界为 1，内部 ans[i][j] = ans[i-1][j-1] + ans[i-1][j]。逐行从上到下填充。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> generate(int n) {
vector<vector<int>> ans(n);
for (int i = 0; i < n; i++) {
ans[i].resize(i + 1, 1);
for (int j = 1; j < i; j++)
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (auto &v : Solution().generate(n)) {
for (int x : v)
cout << x << ' ';
cout << '\n';
}
return 0;
}python
#!/usr/bin/env python3
from typing import List
class Solution:
def generate(self, n: int) -> List[List[int]]:
ans = []
for i in range(n):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = ans[-1][j - 1] + ans[-1][j]
ans.append(row)
return ans
def main():
n = int(input())
for v in Solution().generate(n):
print(*v)
if __name__ == "__main__":
main()复杂度
- 时间复杂度：
。 - 空间复杂度：
，存储结果。
总结
杨辉三角是二维递推的基础：每行依赖上一行，边界初始化为 1，内部由相邻两个值相加。