###### tags: `Leetcode` `easy` `dynamic programming` `python` `c++`

# 118. Pascal's Triangle

## [題目來源:] https://leetcode.com/problems/pascals-triangle/

## 題目:
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:

## 解題思路:
每次拿出最後一層的數組進行->補充下一層新的中間元素

## Python:

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows==1:
            return [[1]]
        res=[[1],[1,1]]
        for i in range(2,numRows):
            cur=[1]
            #每次拿出最後一層的進行補充
            for j in range(len(res[-1])-1):
                cur.append(res[-1][j]+res[-1][j+1])
            cur.append(1)
            res.append(cur)
        return res

if __name__ == '__main__':
    result = Solution()
    ans = result.generate(5)
    print(ans)

## C++

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if (numRows==1)
            return {{1}};
        vector<vector<int>> res={{1},{1,1}};
        for (int i=2; i<numRows; i++){
            vector<int> cur = {1};
            vector<int> last=res.back(); //get last val of vector res
            for (int pos=0; pos<last.size()-1; pos++){
                cur.push_back(last[pos]+last[pos+1]);
            }
            cur.push_back(1);
            res.push_back(cur);
        }
        return res;
    }
};

int main(){
    Solution res;
    vector<vector<int>> ans;
    ans=res.generate(5);
    for (int i=0; i<ans.size(); i++){
        for (int j=0; j<ans[i].size(); j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}