[OJ.leetcode] pascals-triangle-ii

https://oj.leetcode.com/problems/pascals-triangle-ii/

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

/*

단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.

먼저 첫 번째 줄에는 숫자 1을 쓴다.

그 다음 줄을 만들려면, 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다. 예를 들어, 네 번째 줄의 숫자 1과 3을 더하여 다섯 번째 줄의 4가 만들어진다.

수학적으로, 이 구조는 파스칼의 법칙을 사용하여 아래와 같이 표현한다. n 번째 줄의 k 번째 값을 a_{nk}라고 하면, 이 값은

a_{n1} = 1

a_{nn} = 1

a_{nk} = a_{{n-1}{k-1}} + a_{{n-1}{k}} (n, k>1)

따라서 recursive 또는 loop로 파스칼의 삼각형을 표현하는 알고리즘만 잘 짜면 끝. 

*/

class Solution {

    public:

    vector<int> getRow(int rowIndex) {

        vector<int> res;

        

        if(rowIndex == 0) {

            res.push_back(1);

            

            return res;

        } else if(rowIndex == 1) {

            res.push_back(1);

            res.push_back(1);

            

            return res;

        } else{

            res.push_back(1);

            res.push_back(1);

        }

        

        vector<int> temp;

        for(int j=1; j < rowIndex ; j++) {

            

            temp.push_back(1);

            for(int i=0; i < res.size()-1 ; i++) {

               temp.push_back(res[i]+res[i+1]);

            }

            temp.push_back(1);

            

            res = temp;

            temp.clear();

        }

        

        return res;

    }

};