[Leetcode] 120. Triangle

삼각형이 있을 때 위에서부터 원소들을 하나씩 거쳐 내려갔을 때 최소합을 구하는 문제. 모든 경우의 수를 열어놓아야 하기에 가지치기는 할 수 없고 결국은 모든 경로의 합을 알아야 한다. 점화식으로 간단하게 풀 수 있는 문제. 경계조건을 잘 설정하고 인덱싱 처리 잘 해주면 문제없음.

const MAX_VALUE = 10000

function minimumTotal(triangle: number[][]): number {
    const newTriangle = []
    let minSum = MAX_VALUE

    triangle.forEach((row, outerIndex) => {
        if (outerIndex === 0) {
            newTriangle.push(row)

            if (outerIndex === triangle.length - 1) {
                minSum = row[0]
            }
        } else {

        const newRow = row.map((value, innerIndex) => {
            const leftValue = innerIndex - 1 === -1 ? MAX_VALUE : newTriangle[outerIndex - 1][innerIndex - 1]
            const rightValue = innerIndex === row.length - 1 ? MAX_VALUE : newTriangle[outerIndex - 1][innerIndex]
            const newValue = Math.min(leftValue, rightValue) + value

            if (outerIndex === triangle.length - 1) {
                if (newValue < minSum) {
                    minSum = newValue
                }
            }

            return newValue
        })
        
        newTriangle.push(newRow)
        }
    })

    return minSum
};