题目描述

给定一个非负整数$numRows$，生成杨辉三角的前$numRows$行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

算法

递推法

C++ 代码

 class Solution {
 public:
     vector<vector<int>> generate(int n) {
         vector<vector<int> > res;
         vector<int> tmp;
         if (n == 0)
             return res;
         if (n == 1)
         {
             tmp = vector<int>({ 1 });
             res.push_back(tmp);
             return res;
         }
         if (n == 2)
         {
             tmp = vector<int>({ 1 });
             res.push_back(tmp);
             tmp = vector<int>({ 1, 1 });
             res.push_back(tmp);
             return res;
         }
         tmp = vector<int>({ 1 });
         res.push_back(tmp);
         tmp = vector<int>({ 1, 1 });
         res.push_back(tmp);
         for (int i = 2; i < n; ++i)
         {
             tmp = vector<int>(res[i - 1].size() + 1, 1); // 当前层初始化
             for (int j = 1; j < tmp.size() - 1; ++j)
             {
                 tmp[j] = res[i - 1][j - 1] + res[i - 1][j];
             }
             res.push_back(tmp);
         }
         return res;
     }
 };