[프로그래머스] 43105 정수 삼각형(Lv.3) - DP(동적 계획법)

문제

정수 삼각형

문제 해설

문제에는 꼭대기에서 바닥으로 이어지는 경로라고 주어졌지만 이 문제는 상향식(Bottom - up) 방법을 이용하면 쉽게 풀 수 있다.
각 노드의 좌측 아래 노드의 값과 우측 아래 노드의 값을 비교하여 더 큰 값과 현재 노드의 값을 더한 값을 현재 노드 위치에 저장한다. 이 과정을 루트 노드까지 반복하여 루트 노드까지 가는 경로 중 숫자의 합이 최대 값을 찾을 수 있다.

class Solution {
    public int solution(int[][] triangle) {

        int[][] memo = new int[triangle.length][];
        for (int i = 0; i < triangle.length; i++)
            memo[i] = new int[triangle[i].length];

        // memo의 마지막 행의 값을 triangle와 동일하게 설정
        for (int i = 0; i < memo[memo.length-1].length; i++)
            memo[memo.length-1][i] = triangle[triangle.length-1][i];

        for (int i = triangle.length-2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].length; j++) {
                memo[i][j] = Math.max(triangle[i][j] + memo[i+1][j], triangle[i][j] + memo[i+1][j+1]);
            }
        }
        return memo[0][0];
    }
}