pascals-triangle-i

gistfile1.txt

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;
    }
};