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

# 119. Pascal's Triangle II

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

## 題目:
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle. 同P118

**Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?**

## 解題思考:
* 因為只能用O(rowIndex)的空間
* 倒著求下一層的元素!!

## Python:

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        #只能用O(rowIndex)的空間
        res=[1]
        #倒著求 從尾巴逐一更新
        for i in range(rowIndex):
            for j in range(len(res)-1,0,-1):
                res[j]+=res[j-1]
            res.append(1)
        return res

result=Solution()
ans=result.getRow(rowIndex = 4)
print(ans)

## C++:

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

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res={1};
        for (int i=0; i<rowIndex; i++){
            for (int j=res.size()-1; j>0; j--){
                res[j]+=res[j-1];
            }
            res.push_back(1);
        }
        return res;
    }
};

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