118. Pascal's Triangle

problem description

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

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

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

algorithm thought

其实和之前动态规划问题得到数组中的值有的像，此位置的值等于上两个位置的值相加。可以用二维数组解决，但是这里是可以优化到只用一维数组。每次重复使用即可。

code

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if(numRows==0)
            return res;
        vector<int> tmp(1,1);
        res.push_back(tmp);
        while(--numRows){
            tmp.push_back(1);
            for(int i=tmp.size()-2;i>=1;--i){
                tmp[i]+=tmp[i-1];
            }
            res.push_back(tmp);
        }
        return res;
    }
};

algorithm analysis

帕斯卡三角形，三角形面积是O(n²)的，每个点都要计算，最后时间复杂度O(n²)