leecode 解题总结：118. Pascal's Triangle

#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*问题:Given numRows, generate the first numRows of Pascal's triangle.For example, given numRows = 5,Return[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]分析:题目提供一个行数，然后需要你编写出杨辉三角。杨辉三角实际是有二项式系数列表组成。(a+b)^2=a^2 + 2*a*b + b^2(a+b)^n=C(n,k) * a^(n-k) * b^k 累加求和，其中k从0到n以n=4为例，系数为:1 , 4 , 6 , 4, 1。此时对应的numRows=5，所以numRows - 1 = nC(n,0)=C(n,n)=1，以n=5为例，C(5,0)=1,C(5,1)根据传入的函数计算即可。如果每次根据组合公式，计算量很大C(n,k) = n! / ( (k!) * (n-k)! )观察发现：杨辉三角从第三行开始，上一行和下一行之间存在递推关系，下一行处第一个数字和最后一个数字均为1外，设上一行数组为A,下一行数组为B，则有B[i] = A[i-1] + A[i]，其中i >= 2, i <= A.len 输入:015输出:no result11,1,1,1,2,1,1,3,3,1,1,4,6,4,1关键:1 观察发现：杨辉三角从第三行开始，上一行和下一行之间存在递推关系，下一行处第一个数字和最后一个数字均为1外，设上一行数组为A,下一行数组为B，则有B[i] = A[i-1] + A[i]，其中i >= 2, i <= A.len 采用递推来做2 (a+b)^n=C(n,k) * a^(n-k) * b^k 累加求和，其中k从0到nC(n,k) = n! / ( (k!) * (n-k)! )*/class Solution {public:    vector<vector<int>> generate(int numRows) {		vector<vector<int>> results;		//numRows至少为1，		if(numRows < 1)		{			return results;		}		//初始化第一行和第二行，从第三行开始进行地推        for(int i = 1; i <= numRows ; i++)		{			vector<int> result(i , 1);			//开始递推，公式为:			if(i > 2)			{				//这里i-1取不到				for(int j = 1 ; j < i - 1; j++)				{					result.at(j) = results.at(i-2).at(j-1) + results.at(i-2).at(j);				}				results.push_back(result);			}			else			{				results.push_back(result);			}		}		return results;    }};void PRint(vector<vector<int> >& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	int len;	for(int i = 0 ; i < size ; i++)	{		len = result.at(i).size();		for(int j = 0 ; j < len ; j++)		{			cout << result.at(i).at(j) << "," ;		}		cout << endl;	}}void process(){	 int num;	 Solution solution;	 vector<vector<int> > result;	 while(cin >> num )	 {		 result = solution.generate(num);		 print(result);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}