题目：多边形三角剖分的最低得分

  • 给定N，想象一个凸N边多边形，其顶点按顺时针顺序依次标记为A[0], A[i], ..., A[N-1]。
  • 假设您将多边形剖分为N-2个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有N-2个三角形的值之和。
  • 返回多边形进行三角剖分后可以得到的最低分。
示例 1：
输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：

image
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。
提示：
  • 3 <= A.length <= 50
  • 1 <= A[i] <= 100

来源：力扣（LeetCode）第1039题

链接：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon

分析：

  • 可以使用dp或者dfs两种方法(好像很多题我都会这么讲。。。)
  • 这两种方式的思路完全一致，唯一的不同就是一个是递归一个是dp。
  • 我们声明两个状态i，j为从第i个位置开始，到第j个位置为止。
  • 我们发现如果i==j-1的话，是不可能会有答案的，因为中间还要有第三个位置。
  • 至少要i+2==j才行，这样中间才能有一个位置放第三个点。
  • 也就是说如果中间有两个位置，那么第三个点就有两种可能，以此类推。
  • 如果中间有多个位置，我们随便选择其中的一个，一个三角形的三个点就是i,j,k(中间的那个点)，那么另外n-3个三角形的顶点的值要怎么算呢？我们发现除去i,j,k这个三角形外，其他的三角形的值我们在小一维的dp里已经算过了(就是长度比当前长度小1的那些值)。
  • 比如现在我们要找其他的三角形那么其他的三角形的值就是dp[i][k]和dp[k][j]里面，而这两个值肯定已经算过了，因为这两个值所代表的状态肯定比当前状态的长度要小。

代码：

  • dp

    class Solution {
public int minScoreTriangulation(int[] A) {
    int len = A.length;
    int[][] dp = new int[len][len];
    for (int i = 0; i < len; i++) for (int j = 0; j < len; j++) dp[i][j] = Integer.MAX_VALUE;
    for (int i = 0; i < len - 1; i++) dp[i][i+1] = 0;
    for (int d = 2; d < len; d++) { // 长度
        for (int i = 0; i < len - d; i++) {
            int j = i + d;
            for (int k = i + 1; k < j; k++)
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
        }
    }
    return dp[0][len-1];
}
}

  • dfs + 记忆化(不加记忆化会超时)

    class Solution {
private int[][] memo;
public int minScoreTriangulation(int[] A) {
    int len = A.length;
    memo = new int[len][len];
    return dfs(0, len - 1, A);
}

public int dfs(int left, int right, int[] A) {
    if (left + 1 == right) return 0;
    if (memo[left][right] != 0) return memo[left][right];
    int ans = Integer.MAX_VALUE;
    for (int k = left + 1; k < right; k++)
        ans = Math.min(ans, dfs(left, k, A) + dfs(k, right, A) + A[left] * A[k] * A[right]);
    memo[left][right] = ans;
    return ans;
}
}