[LeetCode] 119. Pascal's Triangle II - 문제풀이

Description

파스칼의 삼각형을 계산하여 주어진 rowIndex의 값들을 반환하는 문제입니다.

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:

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints

• 0 <= rowIndex <= 33

Solution 1. Dynamic Programming

public List<Integer> getRow(int rowIndex) {

    List<List<Integer>> triangle = new ArrayList<>();
    for (int i = 0; i <= rowIndex; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if(j==0 || j==i){
                row.add(1);
            }else {
                row.add(triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));
            }
        }
        triangle.add(row);
    }
    return triangle.get(triangle.size()-1);
}

제일 첫번째 ROW부터 탑다운 방식으로 값을 채워나가며 주어진 마지막 rowIndex의 값을 반환해줍니다.

Reference

Pascal's Triangle II - LeetCode