区间dp

-1.枚举区间长度，根据题目来分析
-2.枚举区间起点
-3.根据起点与区间长度，确定区间结束位置(当结束位置超过区间长度，跳出循环)
-4.枚举i-j中每一个位置k把区间分为两部分，更新dp[i][j]

1130. 叶值的最小代价生成树
      给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：

每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

示例：

输入：arr = [6,2,4]
输出：32
解释：
有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

提示：

2 <= arr.length <= 40
1 <= arr[i] <= 15
答案保证是一个 32 位带符号整数，即小于 2^31。
https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values/

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # 由于中序遍历所以从第k位元素(包括自己)都在左子树, k+1到n-1都在右子树
        # 那么问题可以拆分为k的左右两边元素中最大值的乘积+子问题k左边+子问题k右边
        n = len(arr)
        maxVal = [[0]*n for _ in range(n)]
        for j in range(n):
            maxValue = arr[j]
            for i in range(j, -1, -1):
                maxValue = max(maxValue, arr[i])
                maxVal[i][j] = maxValue #存储arr数组中i-j的最大值
        dp = [[0]*n for _ in range(n)]
        # for j in range(n):
        #     for i in range(j, -1, -1):
        #         Min = float("inf")
        #         for k in range(i, j):
        #             Min = min(Min, dp[i][k]+dp[k+1][j]+maxVal[i][k]*maxVal[k+1][j])
        #             dp[i][j] = Min
        # return dp[0][n-1]

        #枚举区间长度
        for l in range(1, n+1):
            #枚举区间起点
            for i in range(n):
                j = i+l
                if j>=n:
                    break
                dp[i][j] = float("inf")
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+maxVal[i][k]*maxVal[k+1][j])
        return dp[0][n-1]

1039. 多边形三角剖分的最低得分
      给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

示例 1：

输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：

输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：375 + 457 = 245，或 345 + 347 = 144。最低分数为 144。
示例 3：

输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 113 + 114 + 115 + 111 = 13。

提示：

3 <= A.length <= 50
1 <= A[i] <= 100
https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/

class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        n = len(A)
        dp = [[0]*n for _ in range(n)]
        # for j in range(2, n):
        #     for i in range(j-2, -1, -1):
        #         for k in range(i+1, j):
        #             if dp[i][j]==0:
        #                 dp[i][j] = A[i]*A[j]*A[k]+dp[i][k]+dp[k][j]
        #             else:
        #                 dp[i][j] = min(dp[i][j], A[i]*A[j]*A[k]+dp[i][k]+dp[k][j])
        # return dp[0][n-1]

        #枚举区间长度
        for l in range(2, n+1):
            #枚举区间起点
            for i in range(n):
                j = i+l
                if j>=n:
                    break
                dp[i][j] = float("inf")
                for k in range(i+1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+A[i]*A[j]*A[k])
        return dp[0][n-1]