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

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/
Star
给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例 1：
输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：
notion imagenotion image
输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
示例 3：
输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
提示：
  1. 3 <= A.length <= 50
  1. 1 <= A[i] <= 100

法1 动态规划 区间型

思路
找到子问题，再找子问题之间的关系。
dp[i][j] 表示将values[i:j+1] 剖分后得到的分数。显然dp[i][i] = 0 dp[i][i+1] = 0
观察下图，假设i=1，j=6,那么刨分点k 可以为[2,3,4,5]，可以有如下多种得分：
  • 刨分点k=2, dp[i][j] = values[1]*values[2]*values[6] + dp[1][2] + dp[2][6]
  • 刨分点k=3, dp[i][j] = values[1]*values[3]*values[6] + dp[1][3] + dp[3][6]
  • 刨分点k=4, dp[i][j] = values[1]*values[4]*values[6] + dp[1][4] + dp[4][6]
  • 刨分点k=5, dp[i][j] = values[1]*values[5]*values[6] + dp[1][5] + dp[5][6]
notion imagenotion image
题解
class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        dp = [[float('inf')]*len(values) for _ in values]
        # dp[i][j] 表示 蒋values[i][j] 之间的三角形刨分得到的最小值
        # 显然 dp[i][i] = 0 and dp[i][i+1] = 0
        for i in range(0, len(values)):
            dp[i][i] = 0
            if i < len(values)-1:
                dp[i][i+1] = 0
    
        for i in range(len(values)-1, -1, -1):
            for j in range(i+2, len(values), 1):
                for k in range(i+1, j):
                    dp[i][j] = min(dp[i][j], 
                                    values[i]*values[k]*values[j]+dp[i][k]+dp[k][j])

        return dp[0][-1]