TIL _ 동적계획법 _ 0811 _ SUN

오늘의 문제 _ 118. Pascal's Triangle(LeetCode)

줄이 늘어날 수록 숫자의 갯수는 1씩 증가하고 맨 처음 값과 맨 마지막 값은 각각 1이다.

나머지 값들은 윗줄의 (col -1) + 윗줄의 col 값 (col은 해당 숫자가 그 줄의 몇번째에 있는지를 나타냄)

 

나의 풀이

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();

        if(numRows == 0){
            return triangle;
        }
        
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        triangle.add(firstRow);

        for(int i=1; i<numRows; i++){
            List<Integer> prevRow = triangle.get(i-1);
            List<Integer> currentRow = new ArrayList<>();

            currentRow.add(1);

            for(int j=1; j<i; j++){
                currentRow.add(prevRow.get(j-1) + prevRow.get(j));
            }

            currentRow.add(1);

            triangle.add(currentRow);
        }
        return triangle;
    }
}

 

나의 회고

삼각형의 각 행을 저장할 리스트를 만들어 준 후 numRows가 0인 경우 빈 삼각형을 반환했고, 

첫번째 행은 항상 1로 시작하여 n번째 행까지 생성 → triangle.add(firstRow);

각 행의 첫번째 요소와 마지막 요소는 1이며 행의 중간 요소는 이전 행의 두 요소의 합으로 만들어줌

 → currentRow.add(prevRow.get(j-1) + prevRow.get(j));

마지막으로 완성된 행을 삼각형에 추가해주었다.