삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾기

→ 지금까지 겨쳐간 누적 합이 필요하므로 주어진 삼각형과 똑같은 크기의 table 만들기

예제를 살펴보면, 각 행 별로 양 끝 index를 제외한 중간 index는 양 방향에서 값이 내려온다.

• num1 = 좌측 방향에서 내려오는 누적 합
• num2 = 우측 방향에서 내려오는 누적 합

따라서 이 두 수 중 큰 값을 DP table에 저장한다면 다음 행들의 누적 합을 구할 때 최대값 만을 고려하게 될 것이다!

→ 정답은 마지막 행의 배열 중 최대값이다.

풀이 코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        //누적 합을 위한 배열 -> triangle과 동일한 크기
        int[][] sum = new int[triangle.length][];
        for(int i=0; i<triangle.length; i++) {
            sum[i] = new int[triangle[i].length];
        }
        
        //start
        sum[0][0] = triangle[0][0];
        
        for(int i=1; i<triangle.length; i++) {
            
            sum[i][0] = sum[i-1][0] + triangle[i][0];
            
            **/* 중간 index */
            for(int j=1; j<sum[i].length-1; j++) {
                int num1 = sum[i-1][j-1] + triangle[i][j];
                int num2 = sum[i-1][j] + triangle[i][j];
                
                sum[i][j] = Math.max(num1, num2);
            }
            /* 중간 index 끝 */**
            
            sum[i][sum[i].length - 1] 
                = sum[i-1][sum[i-1].length - 1] + triangle[i][sum[i].length - 1];
        }
        
        //마지막 배열의 최대값이 정답
        answer = sum[triangle.length - 1][0];
        for(int i=1; i<sum[triangle.length - 1].length; i++) {
            if(sum[triangle.length - 1][i] > answer)
                answer = sum[triangle.length - 1][i];
        }
        
        return answer;
    }
}