LeetCode 120 - Triangle

Triangle - LeetCode

 

삼각형 형태의 배열이 주어졌을 때 top에서 bottom까지 최소 합의 경로를 찾아라.

매 단계에서 아래행의 인접한 숫자로 이동할 수 있다. 배열로 치면 현재 (r, c)에 있다고 했을 때 (r + 1, c) 혹은 (r + 1, c + 1)로 이동이 가능한 것이다.

우선 top에서 bottom까지 매 순간 다양한 경로가 존재한다. 먼저 떠오르는 방식은 dfs를 사용하는 완전탐색이다.

하지만 이 방법은 당연하게도 시간초과가 발생한다.

top에서 bottom으로 가는 것을 bottom에서 top으로 간다고 생각해보겠다.

가장 위 (0, 0)의 최소합은 (1, 0), (1,1) 이 두 포인트의 최소합 중 최소에 (0,0) 값을 더한 것이다.

즉 (r, c)의 최소합은 Math.min((r + 1, c), (r + 1, c + 1)) + (r, c)가 된다.

class Solution {
    static final int[][] DIRECTION = {{1, 0}, {1, 1}};
    static final int INF = Integer.MAX_VALUE;

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int[][] mem = new int[triangle.size()][triangle.size()];
        for (int[] row : mem) {
            Arrays.fill(row, INF);
        }
        
        return dfs(0, 0, triangle, mem);
    }

    private int dfs(int r, int c, List<List<Integer>> triangle, int[][] mem) {
        if (r == triangle.size()) {
            return 0;
        }

        if (mem[r][c] != INF) {
            return mem[r][c];
        }

        int min = INF;
        for (int d = 0; d < 2; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];
            
            min = Math.min(min, dfs(nr, nc, triangle, mem));
            
        }
        
        return mem[r][c] = min + triangle.get(r).get(c);
    }
}

top-down방식의 dp이다. 재귀를 통해 하단부터 최솟값을 채워 나갔다.

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] mem = new int[triangle.size()][triangle.size()];
        int n = triangle.size() - 1;
        for (int r = n - 1; r >= 0; r--) {
            for (int c = 0; c < triangle.get(r).size(); c++) {
                triangle.get(r).set(c, Math.min(triangle.get(r+1).get(c), triangle.get(r + 1).get(c + 1)) + triangle.get(r).get(c));
            }
        }

        return triangle.get(0).get(0);
    }
}

bottom-up 방식의 dp이다. 재귀 없이 반복문으로도 처리가 가능하다. 그리고 별도의 배열을 사용하지 않아 공간효율이 늘었다.