题目描述

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

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

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

样例

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

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

输入：[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

算法1

(动态规划) $O(n^3)$

1. 我们首先分析一下划分的过程。假设一开始所有点之间都没有连线（包括相邻的点），我们任选两个点 $(s, t)$ 作为初始的点对，将 $s$ 和 $t$ 连线。
2. 此时整个凸多边形被划分为两段连续的部分。对于其中一部分，任选一个没有被连接的点 $u$，与 $s$ 和 $t$ 分别连线，组成一个三角形，则 $(s, u)$ 和 $(u, t)$可以将那一部分进一步划分。
3. 通过这样的分析，我们可以看出，每次划分的都是连续的一段区间，我们从连续的一段区间中找到一个点，将这段连续的区间划分为更小的区间，这显然满足区间动态规划的基本模型。
4. 因为图形是环形的，首先考虑将点拷贝一份接到最后，即 A[0], A[1], ..., A[N - 1], A[0], A[1], ..., A[N - 1]，共计 $2n$ 个点。设状态 $f(i, j)$ 表示划分区间 $[i, j]$ 的最小代价（其中点对 $(i, j)$ 已经连线）。
5. 初始值 $f(i, i + 1) = 0$。转移时，枚举除了 $i$ 和 $j$ 之外的点 $k$，让 $i, j, k$ 组成一个三角形，即 $f(i, j) = \min (f(i, j), f(i, k) + f(k, j) + A[i] * A[j] * A[k])$。
6. 找最终答案时，需要枚举初始的连线 $(i, j)$，$0 \le i < j < n$，找 $\min (f(i, j) + f(j, i + n))$。

时间复杂度

• 状态数为 $O(n^2)$，每次转移需要枚举 $O(n)$ 个状态，故时间复杂度为 $O(n^3)$。

空间复杂度

• 需要记录状态，故空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        const int MAX = 100000000;
        int n = A.size();
        for (int i = 0; i < n; i++)
            A.push_back(A[i]);

        vector<vector<int>> f(2 * n, vector<int>(2 * n, MAX));

        for (int i = 0; i < 2 * n - 1; i++)
            f[i][i + 1] = 0;

        for (int len = 3; len <= n; len++)
            for (int i = 0; i < 2 * n - len + 1; i++) {
                int j = i + len - 1;
                for (int k = i + 1; k < j; k++)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + A[i] * A[j] * A[k]);
            }

        int ans = MAX;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                ans = min(ans, f[i][j] + f[j][i + n]);
        return ans;
    }
};

算法2

(动态规划) $O(n^3)$

1. 基于算法1，我们能进行一些常数上的优化。我们发现，最后的最优答案中，必定相邻的两个点会进行连线，所以我们不妨先连上 $(0, n - 1)$ 这两个点（其余的点仍然不连线）。
2. 然后仍然按照算法1的思路进行动态规划，最终答案也就是 $f(0, n - 1)$ 了。

时间复杂度

• 状态数为 $O(n^2)$，每次转移需要枚举 $O(n)$ 个状态，故时间复杂度为 $O(n^3)$。

空间复杂度

• 需要记录状态，故空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        const int MAX = 100000000;
        int n = A.size();

        vector<vector<int>> f(n, vector<int>(n, MAX));

        for (int i = 0; i < n - 1; i++)
            f[i][i + 1] = 0;

        for (int len = 3; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                for (int k = i + 1; k < j; k++)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + A[i] * A[j] * A[k]);
            }

        return f[0][n - 1];
    }
};