LC.P1039[多边形三角剖分的最低得分]

题目描述

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

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

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

示例 1：

shape1

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

示例 2：

shape2

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

示例 3：

shape3

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

提示：

  • n == values.length
  • 3 <= n <= 50
  • 1 <= values[i] <= 100

方法一：区间DP+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    
    int[] v;
    int[][] cache;

    public int minScoreTriangulation(int[] values) {
        v = values;
        int n = values.length;
        cache = new int[n][n];
        return dfs(0, n - 1);
    }

    private int dfs(int i, int j) {
        if (i + 1 == j) return 0; // 只有两个点，无法组成三角形
        if (cache[i][j] != 0) return cache[i][j];
        int ans = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; ++k) { // 枚举顶点k
            ans = Math.min(ans, dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]);
        }
        return cache[i][j] = ans;
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^2)$

方法二：1:1翻译成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] f = new int[n][n];
        for (int i = n - 3; i >= 0; --i) {
            for (int j = i + 2; j < n; ++j) {
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; ++k) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        return f[0][n - 1];
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^2)$