[JAVA] 프로그래머스 LEVEL3 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형

 

난이도: LEVEL3

알고리즘 유형: 다이나믹 프로그래밍 

정답 코드 

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length; // 삼각형 높이 & 밑변
        for(int i = n - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                triangle[i][j] += Math.max(triangle[i+1][j], triangle[i+1][j+1]);
            }    
        }
        return triangle[0][0];
    }
}

 

삼각형 아래에서 위로 누적해서 올라간다.

 

점화식 

triangle[i][j] = triangle[i][j] (본인 정점이 가지는 값) + Math.max(triangle[i+1][j], triangle[i+1][j+1])