【LeetCode】118. Pascal's Triangle

问题描述

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]
]

分析

设f(i,j)表示第i行第j个数，则有：

f(i,j) =  1,                        i=0
       =  1,                        i>=1, j=0 或 i>=1, j=i-1
       = f(i-1, j-1) + f(i-1, j),   i>=1，j>=1 

代码

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
    	vector<vector<int> > r(numRows);
        if(numRows == 0) return r;
        vector<int> r1;
        r1.push_back(1);
        r[0]=r1;
        for(int i=1;i<numRows;i++) {
        	int j=0;
        	vector<int> t(i+1);
        	t[j++]=1;
        	for(;j<i;j++) {
	        	t[j] = r[i-1][j-1]+r[i-1][j];
	        }
	        t[j]=1;
	        r[i] = t;
        }
        return r;
    }	
};