题目：给定 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中数据的特点，再修改算法。

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

法二：