118. 杨辉三角
3 min
题目
解法：动态规划
思路
第一段：采用动态规划思想，逐行递推构造，每行的每个元素依赖于前一行相邻两个元素的和。
第二段：正确性基于数学归纳法。基础情况第0行[1]符合定义。假设前i-1行已正确生成，则第i行的首尾元素恒为1，中间元素通过ans[i-1][j-1] + ans[i-1][j]计算，这恰好满足杨辉三角的组合数学性质C(i,j) = C(i-1,j-1) + C(i-1,j)，因此每行都能被准确构造，不会遗漏任何正确结果。
第三段：
- Step 1: 初始化结果数组ans，从第0行开始迭代
- Step 2: 第0行直接添加{1}
- Step 3: 对于第i行(i>0)，创建临时数组tmp
- Step 4: 遍历j从0到i，首尾位置添加1，中间位置添加ans[i-1][j-1] + ans[i-1][j]
- Step 5: 将tmp加入ans，继续下一行直到完成numRows行
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>>ans;
for(int i = 0;i < numRows;i++){
if(i == 0){
ans.push_back({1});
}
else{
vector<int>tmp;
for(int j=0;j <= i;j++){
if(j > 0){
if(j == i){
tmp.push_back(ans[i-1][i-1]);
}
else{
tmp.push_back(ans[i-1][j-1] + ans[i-1][j]);
}
}
else{
tmp.push_back(1);
}
}
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>>ans;
for(int i = 0;i < numRows;i++){
if(i == 0){
ans.push_back({1});
}
else{
vector<int>tmp;
for(int j=0;j <= i;j++){
if(j > 0){
if(j == i){
tmp.push_back(ans[i-1][i-1]);
}
else{
tmp.push_back(ans[i-1][j-1] + ans[i-1][j]);
}
}
else{
tmp.push_back(1);
}
}
ans.push_back(tmp);
}
}
return ans;
}
};