题目描述：
凸多边形，每个顶点有一个整数值 $value[i]$ 。假设将多边形剖分成 $n - 2$ 个多边形。对于每个三角形，权值是三个顶点的权值乘积，该凸多边形的分数是剩余的所有 $n - 2$ 个三角形的值之和。
返回可以得到的最低权值。
数据范围：
$3\le n \le 50;1\le value[i] \le 100$
题解：
容易想到使用 $dp$ ，也可以得到 $dp$ 方程
因为 $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]$ 区间的长度。
也可以使用记忆化搜索。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution
{
public:
int minScoreTriangulation(vector<int> &values)
{
int n = values.size();
int dp[n][n];
memset(dp, 0, sizeof dp);
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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution
{
public:
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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution
{
public:
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);
}
};
|