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

题目:给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。返回多边形进行三角剖分后可以得到的最低分。

来源:https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/

法一:自己的代码    与戳气球代码类似

思路:先要读懂题意,这个题是只能剖分边上的三角形,可以理解为只切一刀就切出一个三角形,如果要是可以任意切,那这个题就无法求解了,因为涉及到不同数字的合并问题,题中并没有说,所以是只切边上的三角形.

注意这是个环形问题,所以在两边加上两个数字,动态规划最后合并的时候只要中间剩下三个数字就可停止,比如原先是长度为6的数组,2,3,4,5,6,1.先补数字左边补1,右边补2,1 2 3 30 2 中间是2 4 30 30这个是合并后的,此时中间的2 3事实上已经都用过了,所以不能再合并了,30就是最后的结果。这些问题可以先用简单的数字输出结果,观察dp中数据的特点,再修改算法。

1039多边形三角剖分的最低得分
from typing import List
class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        ans = 0
        # 为了方便后续写状态转移方程,添加边界条件
        nums = [A[-1]] + A + [A[0]]
        size = len(nums)
        dp = [[0] * size for i in range(size)]
        # 注意这里size-3,右上角的三个不需要输出
        for start in range(1, size-3):
            i = 1
            print('-' * 20)
            for j in range(start, size - 1):
                print(i, j)
                # 同戳气球的一样
                dp[i][j] = min(nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]
                               for k in range(i, j + 1))
                i += 1
        print(dp)
        return min(dp[1][size - 4], dp[2][size-3], dp[3][size-2])
if __name__ == '__main__':
    duixiang = Solution()
    a = duixiang.minScoreTriangulation( A=[1,3,1,4,1,5])
    # a = duixiang.minScoreTriangulation( A=[3,7,4])
    print(a)
View Code

法二:

上一篇:算法实验一:动态规划


下一篇:动态规划——最长公共子序列(LCS)