LC1039. 多边形三角剖分的最低得分

题目链接：1039. 多边形三角剖分的最低得分

题解

• 区间 DP，假设 $dp[i][j]$ 为从 i 到 j 进行三角剖分后最低分。枚举 i 到 j 中间存在一个点 k，使多边形变成三部分：ik, kj 以及 ijk 三角形的多边形，取最小的就是 ij 的最低分。

• 用 DFS 来写比直接写出递推公式简单一些。

• 看了标签和官方题解才写出来！

参考代码

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        mp = {}
        def dp(i, j):
            if j - i < 2:
                return 0
            if j - i == 2:
                return values[i]*values[i+1]*values[j]
            if (i,j) in mp:
                return mp[(i,j)]
            ans = 1e9
            for k in range(i+1, j):
                tmp = dp(i, k) + dp(k, j) + values[i]*values[k]*values[j]
                ans = min(tmp, ans)
            mp[(i,j)] = ans
            return ans

        return dp(0, len(values)-1)

错误贪心

• 枚举一个点做为顶点，往其他点连线将平面且分成 n-2 个三角形，样例第三个都过不了……

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        aa = values + values
        ans = 1e9+7
        for i in range(n):
            tmp = 0
            for j in range(1, n-1):
                tmp += aa[i] * aa[i+j] * aa[i+j+1]
            print(tmp)
            ans = min(tmp, ans)
        return ans