[LeetCode] 120. Triangle - 문제풀이

Description

주어진 삼각형형태의 array 목록에서 맨아래로 갈 수 있는 최단거리를 반환하는 문제입니다.

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

Follow up:

Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Solution 1. Dynamic Programming (bottom-up)

public int minimumTotal(List<List<Integer>> triangle) {
    int m = triangle.size();
    int n = triangle.get(m-1).size();

    int[][] dp = new int[m][n];
    int min = Integer.MAX_VALUE;
    dp[0][0] = triangle.get(0).get(0);
    if(m==1)return dp[0][0];
    for (int i = 1; i < m; i++) {
        List<Integer> cur = triangle.get(i);
        for (int j = 0; j < cur.size(); j++) {
            if(j==0){
                dp[i][j] = cur.get(j) + dp[i-1][j];
            }else if(j==cur.size()-1){
                dp[i][j] = cur.get(j) + dp[i-1][j-1];
            }else{
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + cur.get(j);
            }
            if(i == m-1){
                min =  Math.min(dp[i][j],min);
            }
        }
    }

    return min;
}

상향식(bottom up) 방식의 동적프로그래밍을 이용해서 처리가 가능합니다. 각 레이어의 요소마다의 최소 경로를 기록할 dp공간을 할당하여 맨 끝 요소는 각각 이전 레이어(i-1)의 j의 거리와 j-1요소값 + 자기자신의 비용을 합친 값이고 그오 ㅣ요소는 가능한 두가지 루트중 최소값입니다.

이런식으로 모두 더해 나간 뒤 마지막 레이어의 요소중에 최소값이 최소 거리값 입니다.

Solution 2. Dynamic Programming (top-down)

public int minimumTotal(List<List<Integer>> triangle) {
    // corner case
    if(triangle == null || triangle.size() == 0) return 0;

    // M[i] represents the min total from bottom to current position
    // copy the last row in triangle to M
    int m = triangle.size();
    int n = triangle.get(m - 1).size();
    int[] M = new int[n];
    for(int i = 0; i < n; i++){
        M[i] = triangle.get(m - 1).get(i);
    }

    // induction rule
    // M[i] = min(M[i], M[i + 1]) + curVal
    for(int i = n - 2; i >= 0; i--){
        List<Integer> cur = triangle.get(i);
        for(int j = 0; j < cur.size(); j++){
            M[j] = Math.min(M[j], M[j + 1]) + cur.get(j);
        }
    }

    return M[0];
}

반대방향 하향식(top-down)으로 맨마지막 row부터 내려오며 동적으로 최소값을 계산해 나가는 방법입니다.

Reference

Triangle - LeetCode