LeetCode - Triangle

https://leetcode.com/problems/triangle/

Triangle - LeetCode

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let n = triangle.length;
    for(let i = 1 ; i <n; i++){
        for(let j = 0; j <=i ; j++){
            if(j==0){
                triangle[i][j] += triangle[i-1][j]
            }else if(j==i){
                triangle[i][j] += triangle[i-1][j-1];
            }else{
                let min = Math.min(triangle[i-1][j], triangle[i-1][j-1])
                triangle[i][j] += min;
            }
        }
    }
    return Math.min(...triangle[n-1]);
};

전형적인 DP 문제로,

 

루트 노드가 있는 곳을 1층이라고 했을떄

 

N층의 X번째 노드는 N-1층의 X-1,X 중 제일 큰 것 + 자기 자신의 값과 같다.

 

예외적으로 해당 층의 0번쨰 인덱스나 마지막 인덱스는 선택지가 하나밖에 없으니 고려해줘야한다.