[프로그래머스 알고리즘 고득점 Kit][동적계획법(Dynamic Programming))][Java] 정수 삼각형

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

프로그래머스

위에서부터 내려온다고 가정하면 바로 아래 왼쪽 값이 더 크다고 해서 그 경로가 최대로 가는 경로가 아닐 수 있음

그래서 생각하기 어려움

밑에서부터 올라간다고 생각하면
특정 노드를 기준으로 최대가 되려면 밑에 2개의 값 중 큰 것만 고르면됨
그렇게 맨 밑에서 부터 큰 값들을 골라서 위로 올라가면 최종엔 최대 합만 남음

class Solution {
    public int solution(int[][] triangle) {
        int N = triangle.length;
        for(int i=N-1; i>0; i--){
            for(int j=0; j<i; j++){
                triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
            }
        }
        return triangle[0][0];
    }
}