[Leetcode] 1039. Minimum Score Triangulation of Polygon

주어진 다각형 안에서 정점을 이어서 삼각형으로 만든다. 이때 만들어진 모든 삼각형의 세 꼭지점의 각 정점에 있는 weight 를 곱한 뒤 최소값을 구해야 한다(O(N^3)임을 알 수 있다). 모든 경우의 수를 고려해봐야 하고 최소값을 구하기 위해 이전값의 결과와 비교해가며 계산을 해야 하기에 memoization 이 필수적으로 요구된다.

삼각형을 만들기 위해 필요한 점은 세 개이므로 len=2 로 놓고 점차 늘려가면서 이전 값과 비교한다. dp[i][j] vs dp[i][k] + n[i]*n[k]*n[j] + dp[k][j] 의 값을 하나씩 비교해나가면 된다. 중간에 경유하는 정점인 k 가 망가지지 않고 초기값을 구할 수 있도록 i 값이 바뀔 때 마다 해당 행을 Infinity 로 초기화시켜주면서 돌면 된다.

function minScoreTriangulation(values: number[]): number {
    const n = values.length

    const dp = Array.from({ length: n }, () => Array(n).fill(0))

    for (let len = 2; len < n; len++) {
        for (let i = 0; i < n - len; i++) {
            const j = i + len

            dp[i][j] = Infinity

            for (let k = i + 1; k < j; k++) {
                const weight = values[i] * values[k] * values[j]
                const newWeight = dp[i][k] + dp[k][j] + weight

                dp[i][j] = Math.min(dp[i][j], newWeight)
            }
        }
    }

    return dp[0][n - 1]
};

2차원 배열을 쓰는 DP 에서 주의할 점이 많은데 오랜만에 푸니까 솔직히 너무 힘들었다. 이게 왜 난이도 미디엄인지 모르겠다...