1. 题目

1.1 英文题目

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

1.2 中文题目

给定行数，构造杨辉三角形

1.3输入输出

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

1.4 约束条件

• 1 <= numRows <= 30

2. 实验平台

IDE：VS2019
IDE版本：16.10.1
语言：c++11

3. 程序

3.1 测试程序

#include "Solution.h"
#include <vector>	// std::vector
#include<iostream>	// std::cout
using namespace std;

// 主程序
int main()
{
	// 输入
	int numRows = 30;

	Solution solution; // 实例化Solution
	vector<vector<int>> output = solution.generate(numRows); // 主功能
}

3.2 功能程序

3.2.1 最优算法

（1）代码

#pragma once
#include<vector>    // std::vector
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>> r(numRows);

        for (int i = 0; i < numRows; i++) {
            r[i].resize(i + 1);
            r[i][0] = r[i][i] = 1;

            for (int j = 1; j < i; j++)
                r[i][j] = r[i - 1][j - 1] + r[i - 1][j];
        }

        return r;
    }
};

参考：https://leetcode.com/problems/pascals-triangle/discuss/38171/Maybe-shortest-c%2B%2B-solution

（2）解读

大牛的最短c++代码

3.2.1 自写算法

（1）代码

#pragma once
#include<vector>    // std::vector
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > ans; // 定义结果
        for (int i = 0; i < numRows; i++) // 按行遍历
        {
            vector<int> anstemp; // 储存一行中每个元素的值
            anstemp.push_back(1); // 每行第一个元素为1
            int j = 1; // 定义每行的元素序号
            while(j < i) // 如果该元素不是开头或结尾
            {
                int temp = ans[i - 1][j - 1] + ans[i - 1][j];
                anstemp.push_back(temp);
                j++;
            }
            if (i > 0) anstemp.push_back(1); // 每行最后一个元素是1
            ans.push_back(anstemp);
        }
        return ans;
    }
};

(2)解读

需要特别注意的是每行的首尾元素，其他的都可以递推得到

4.其他知识

（1）C++可以连等赋值，即a=b=1;