TIL _ 동적계획법 _ 0812 _ MON

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

나의 풀이

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> triangle = new LinkedList<Integer>();

        for(int i=0; i<=rowIndex; i++){
            triangle.add(0,1);
            for(int j=1; j<i; j++){
                triangle.set(j, triangle.get(j) + triangle.get(j+1));
            }
        }
        return triangle;
    }
}

 

나의 회고

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

어제와 비슷하지만 좀 더 간결한 방식으로 풀 수 있었다.

 

덧

부르트 포스 + 메모이제이션 방식을 사용한 코드

class Solution {
    public static Map<Integer,List<Integer>> buf = new HashMap<Integer,List<Integer>>();
    public static int maxRow = 0;
    
    public List<Integer> getRow(int rowIndex) {
        List<Integer> prev = null;
        List<Integer> result = new ArrayList<Integer>();
        int start = maxRow;
        if(buf.containsKey(rowIndex)) return buf.get(rowIndex);
        result.add(1);

        for (int i = start; i <= rowIndex; i++) {
            prev = result;
            result = new ArrayList<Integer>();
            result.add(1);
            if(i > 0) {
                if(i > 1) result.add(i);
                if(buf.containsKey(i)) {
                    result = buf.get(i);
                } else {
                    int idx = i % 2 == 0 ? (i / 2) + 1 : (i + 1) / 2;
                    for (int j = 2; j < idx; j++) {
                        if(i % 2 == 1) {
                            result.add(prev.get(j - 1) + prev.get(j));
                        } else {
                            if(j == idx - 1) {
                                result.add(prev.get(j - 1) + prev.get(j - 1));
                            } else if(j < idx) {
                                result.add(prev.get(j - 1) + prev.get(j));
                            }
                        }
                    }
                    for (int j = result.size() - 1; j >= 0; j--) {
                        if(i % 2 == 0 && j == result.size() - 1) continue;
                        result.add(result.get(j));
                    }
                }
                buf.put(i, result);
                if(maxRow < rowIndex) maxRow = rowIndex;
            }
        }
        return result;
    }
}