(Leet Code JS)Triangle

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

Triangle - LeetCode

 

DP 알고리즘.

삼각형으로 이뤄진 배열에서 최소합을 구하면 된다.

최소합을 구하는 조건은 다음 행의 인접한 두 수 중 더 작은 값을 현재 행 값과 더하면 된다.

 

const minimumTotal = (triangle) => {
    const length = triangle.length;
    
    for(let i = length - 2; i >= 0; i--){
        for(let j = 0; j < triangle[i].length; j++){
            triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    
    return triangle[0][0];
};