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

 

Description

배열을 이용하여 파스칼의 삼각형(Pascal's Triangle)을 구현하는 문제입니다.

Given an integer numRows, return the first numRows of Pascal's triangle.

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

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

• 1 <= numRows <= 30

Solution 1. Dynamic Programming

public List<List<Integer>> generate(int numRows) {

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    for (int i = 0; i < numRows; i++) { // row
        List<Integer> currRow = new ArrayList<Integer>();
        for (int j = 0; j <= i; j++) { // column
            if(j == 0 || j == i){
                currRow.add(1);
            }else{
                Integer left = result.get(i-1).get(j-1);
                Integer right = result.get(i-1).get(j);
                currRow.add(left+right);
            }
        }
        result.add(currRow);
    }
    return result;
}

동적 프로그래밍(Dynamic Programming)을 이용하여 상단부터 Row를 만들어 나갑니다. row의 시작점인 0과 끝점인 i=j가 일치하는 경우는 1이 반환되고 나머지 가운데 위치에서는 이전 row의 j-1과 j의 값을 더해서 넣어줍니다.

Reference

Pascal's Triangle - LeetCode