[LeetCode] 119. Pascal's Triangle II

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

Pascal's Triangle II - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Easy

 

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

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

rowIndex가 주어진다. 0-indexed의 파스칼의 삼각형에서  rowIndex번째 행을 반환하시오.

 

풀이

1. 파스칼의 삼각형을 만들기:

dp테이블을 만들어서, 양 끝인경우 1을, 아니라면 이전 행에서 같은 열과 그 이전의 열의 값을 더한 값을 저장시킨다.

 

2. 누적시키기:

1차원 배열을 만들어서, 이전 값을 계속 누적시키는 방법이 있다.

 

코드

C++ - 파스칼의 삼각형 만들기

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        vector<vector<int>> pasCalTriangle(rowIndex+1, vector<int>(rowIndex+1, 1));

        for(int i = 0; i <= rowIndex; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    continue;
                } else {
                    pasCalTriangle[i][j] = pasCalTriangle[i-1][j-1] + pasCalTriangle[i-1][j];
                }
            }
        }

        return pasCalTriangle[rowIndex];
    }
};

 

Swift - 파스칼의 삼각형 만들기

class Solution {
    func getRow(_ rowIndex: Int) -> [Int] {
        var pascalTriangle = Array(repeating: Array(repeating: 1, count: rowIndex + 1), count: rowIndex + 1)

        for i in 0...rowIndex {
            for j in 0..<i {
                if j == 0 || j == i {
                    pascalTriangle[i][j] = 1
                } else {
                    pascalTriangle[i][j] = pascalTriangle[i-1][j-1] + pascalTriangle[i-1][j]
                }
            }
        }

        return pascalTriangle[rowIndex]
    }
}

 

dart - 누적시키기

class Solution {
  List<int> getRow(int rowIndex) {
    List<int> pascalTriangle = List.filled(rowIndex + 1, 0);
    pascalTriangle[0] = 1;

    for (int i = 1; i <= rowIndex; i++) {
        int prev = 1;
        for (int j = 1; j < i; j++) {
            int temp = pascalTriangle[j];
            pascalTriangle[j] += prev;
            prev = temp;
        }
        pascalTriangle[i] = 1;
    }

    return pascalTriangle;
    }

}