You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the ith vertex in clockwise order.
Polygontriangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles.
You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles.
Return the minimum possible score that you can achieve with some triangulation of the polygon.
Input: values =[3,7,4,5]Output: 144Explanation: There are two triangulations,with possible scores:3*7*5+4*5*7=245, or 3*4*5+3*4*7=144.The minimum score is144.
We exploit the fact that any optimal triangulation of a convex polygon is formed by choosing, for each sub-polygon (interval of vertices) [i..j], one vertex k (i < k < j) to make triangle (i,k,j) plus optimal triangulations of the two resulting sub-polygons (i..k) and (k..j).
Pick every possible third vertex k between i and j to form triangle (i,k,j), then recursively solve the left and right sub-polygons. This brute-force explores all Catalan-like partitions with massive recomputation.
classSolutionNaive {
public:int minScoreTriangulation(std::vector<int>& values) {
int n = values.size();
returndfs(values, 0, n-1);
}
private:int dfs(const std::vector<int>& v, int i, int j) {
if (j - i <2) return0;
int best = INT_MAX;
for (int k = i +1; k < j; ++k) {
best = std::min(best, dfs(v,i,k) + v[i]*v[k]*v[j] + dfs(v,k,j));
}
return best;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolutionNaive {
publicintminScoreTriangulation(int[] values) {
return dfs(values, 0, values.length- 1);
}
privateintdfs(int[] v, int i, int j) {
if (j - i < 2) return 0;
int best = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) {
best = Math.min(best, dfs(v,i,k) + v[i]*v[k]*v[j]+ dfs(v,k,j));
}
return best;
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolutionNaive:
defminScoreTriangulation(self, values: list[int]) -> int:
from math import inf
defdfs(i: int, j: int) -> int:
if j - i <2:
return0 best = inf
for k in range(i+1, j):
best = min(best, dfs(i,k) + values[i]*values[k]*values[j] + dfs(k,j))
return best
return dfs(0, len(values)-1)
classSolutionMemo {
public:int minScoreTriangulation(std::vector<int>& values) {
int n = values.size();
memo.assign(n, std::vector<int>(n, -1));
returnsolve(values, 0, n-1);
}
private: std::vector<std::vector<int>> memo;
intsolve(const std::vector<int>& v, int i, int j) {
if (j - i <2) return0;
int&ref = memo[i][j];
if (ref !=-1) return ref;
int best = INT_MAX;
for (int k = i +1; k < j; ++k)
best = std::min(best, solve(v,i,k) + v[i]*v[k]*v[j] + solve(v,k,j));
return ref = best;
}
};
classSolutionMemo {
privateint[][] dp;
publicintminScoreTriangulation(int[] values) {
int n = values.length;
dp =newint[n][n];
for (int i = 0; i < n; i++)
java.util.Arrays.fill(dp[i], -1);
return solve(values, 0, n-1);
}
privateintsolve(int[] v, int i, int j) {
if (j - i < 2) return 0;
if (dp[i][j]!=-1) return dp[i][j];
int best = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) {
best = Math.min(best, solve(v,i,k) + v[i]*v[k]*v[j]+ solve(v,k,j));
}
dp[i][j]= best;
return best;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
from functools import lru_cache
classSolutionMemo:
defminScoreTriangulation(self, values: list[int]) -> int:
@lru_cache(None)
defsolve(i: int, j: int) -> int:
if j - i <2:
return0 best = float('inf')
for k in range(i+1, j):
best = min(best, solve(i,k) + values[i]*values[k]*values[j] + solve(k,j))
return best
return solve(0, len(values)-1)
classSolution {
public:int minScoreTriangulation(std::vector<int>& values) {
int n = values.size();
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
for (int len =3; len <= n; ++len) {
for (int i =0; i + len <= n; ++i) {
int j = i + len -1;
int best = INT_MAX;
for (int k = i +1; k < j; ++k)
best = std::min(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]);
dp[i][j] = best;
}
}
return dp[0][n-1];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
publicintminScoreTriangulation(int[] values) {
int n = values.length;
int[][] dp =newint[n][n];
for (int len = 3; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
int best = Integer.MAX_VALUE;
for (int k = i + 1; k < j; ++k)
best = Math.min(best, dp[i][k]+ dp[k][j]+ values[i]*values[k]*values[j]);
dp[i][j]= best;
}
}
return dp[0][n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defminScoreTriangulation(self, values: list[int]) -> int:
n = len(values)
dp = [[0]*n for _ in range(n)]
for length in range(3, n+1):
for i in range(0, n - length +1):
j = i + length -1 best = float('inf')
for k in range(i+1, j):
best = min(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])
dp[i][j] = best
return dp[0][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolutionK {
funminScoreTriangulation(values: IntArray): Int {
val n = values.size
val dp = Array(n) { IntArray(n) }
for (len in3..n) {
for (i in0..n-len) {
val j = i + len - 1var best = Int.MAX_VALUE
for (k in i+1 until j) {
best = minOf(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])
}
dp[i][j] = best
}
}
return dp[0][n-1]
}
}
impl Solution {
pubfnmin_score_triangulation(values: Vec<i32>) -> i32 {
let n = values.len();
letmut dp =vec![vec![0; n]; n];
for len in3..=n {
for i in0..=n-len {
let j = i + len -1;
letmut best =i32::MAX;
for k in i+1..j {
let cand = dp[i][k] + dp[k][j] + values[i]*values[k]*values[j];
if cand < best { best = cand; }
}
dp[i][j] = best;
}
}
dp[0][n-1]
}
}