1039.多边形三角剖分的最低得分

1039.多边形三角剖分的最低得分

题目描述：

凸多边形，每个顶点有一个整数值 $value[i]$ 。假设将多边形剖分成 $n - 2$ 个多边形。对于每个三角形，权值是三个顶点的权值乘积，该凸多边形的分数是剩余的所有 $n - 2$ 个三角形的值之和。

返回可以得到的最低权值。

数据范围：
$3\le n \le 50;1\le value[i] \le 100$

题解：

容易想到使用 $dp$ ，也可以得到 $dp$ 方程

$$dp[i][j] = min(dp[i][k] + dp[k][j] + value[i]\times value[k]\times value[j], dp[i][j]),i\lt k \lt j$$

因为 $dp[i][j]$ 需要知道 $dp[i][k]$ 和 $dp[k][j]$ 的值，其中 $dp[i][k]$ 的值需要对 $j$ 正着枚举， $dp[k][j]$ 的值 $(i\lt k)$ 需要对 $i$ 倒着枚举。

同时注意初始化 $dp[i][j] = 0(i > j + 2)$ 也就是无法组成三角形的，权值是 $0$ 。

也可以使用区间 $dp$ ，直接枚举 $[i,j]$ 区间的长度。

也可以使用记忆化搜索。

代码：

class Solution
{
public:
    // dp[i][j] = dp[i][k] + dp[k][j] + v[i] * v[k] * v[j];
    int minScoreTriangulation(vector<int> &values)
    {
        int n = values.size();
        int dp[n][n];
        memset(dp, 0, sizeof dp);
        // i,j 需要知道 i,k 与 k,j;
        // 因此 j 正着枚举，i 倒着枚举
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i + 2; j < n; ++j)
            {
                dp[i][j] = 0x3f3f3f3f;
                for (int k = i + 1; k < j; ++k)
                {
                    dp[i][j] = min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j], dp[i][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

class Solution
{
public:
    // dp[i][j] = dp[i][k] + dp[k][j] + v[i] * v[k] * v[j];
    int dp[50][50];
    int minScoreTriangulation(vector<int> &values)
    {
        int n = values.size();
        for(int len = 3; len <= n; ++len)
        {
            for(int i = 0; i + len - 1 < n; ++i)
            {
                int j = i + len - 1;
                dp[i][j] = INT_MAX;
                for(int k = i + 1; k < j; ++k)
                {
                    dp[i][j] = min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j], dp[i][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

class Solution
{
public:
    // dp[i][j] = dp[i][k] + dp[k][j] + v[i] * v[k] * v[j];
    int dp[50][50];
    int dfs(int l, int r, vector<int>& values)
    {
        if(r < l + 2) return dp[l][r] = 0;
        if(dp[l][r]) return dp[l][r];
        dp[l][r] = INT_MAX;
        for(int k = l + 1; k < r; ++k)
        {
            dp[l][r] = min(dp[l][r], dfs(l, k, values) + dfs(k, r, values) + values[l] * values[r] * values[k]);
        }
        return dp[l][r];
    }
    int minScoreTriangulation(vector<int> &values)
    {
        int n = values.size();
        
        return dfs(0, n - 1, values);
    }
};