LeetCode 1039: Minimum Score Triangulation of Polygon (Dynamic Programming)
LeetCode 1039Interval DPPolygonToday we solve LeetCode 1039 - Minimum Score Triangulation of Polygon.
Source: https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
English
Problem Summary
Given a convex polygon where values[i] is the value at vertex i, triangulate the polygon so the total triangle score is minimum. A triangle (i, j, k) contributes values[i] * values[j] * values[k].
Key Insight
This is an interval DP. If triangle uses split point k between i and j, then left interval [i, k] and right interval [k, j] are independent.
Optimal Algorithm
Let dp[i][j] be the minimum score to triangulate vertices from i to j. Transition: dp[i][j] = min(dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]) for i < k < j. Compute by increasing interval length.
Complexity Analysis
Time: O(n^3), Space: O(n^2).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minScoreTriangulation(int[] values) {
int n = values.length;
int[][] dp = new int[n][n];
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) {
int score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
dp[i][j] = Math.min(dp[i][j], score);
}
}
}
return dp[0][n - 1];
}
}func minScoreTriangulation(values []int) int {
n := len(values)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
const inf = int(^uint(0) >> 1)
for l := 3; l <= n; l++ {
for i := 0; i+l-1 < n; i++ {
j := i + l - 1
dp[i][j] = inf
for k := i + 1; k < j; k++ {
score := dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]
if score < dp[i][j] {
dp[i][j] = score
}
}
}
}
return dp[0][n-1]
}class Solution {
public:
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
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][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
}
}
}
return dp[0][n - 1];
}
};class Solution:
def minScoreTriangulation(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(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
return dp[0][n - 1]var minScoreTriangulation = function(values) {
const n = values.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let len = 3; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Number.MAX_SAFE_INTEGER;
for (let k = i + 1; k < j; k++) {
const score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
dp[i][j] = Math.min(dp[i][j], score);
}
}
}
return dp[0][n - 1];
};中文
题目概述
给定一个凸多边形，values[i] 表示第 i 个顶点权值。将其三角剖分后，所有三角形分数之和最小。三角形 (i,j,k) 的分数是 values[i] * values[j] * values[k]。
核心思路
这是典型区间 DP。若最后一次选择顶点 k 与 i,j 组成三角形，那么区间 [i,k] 与 [k,j] 可以独立最优。
最优算法
定义 dp[i][j] 为剖分顶点区间 i..j 的最小分数。转移为：dp[i][j] = min(dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])，其中 i < k < j。按区间长度从小到大计算。
复杂度分析
时间复杂度 O(n^3)，空间复杂度 O(n^2)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minScoreTriangulation(int[] values) {
int n = values.length;
int[][] dp = new int[n][n];
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) {
int score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
dp[i][j] = Math.min(dp[i][j], score);
}
}
}
return dp[0][n - 1];
}
}func minScoreTriangulation(values []int) int {
n := len(values)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
const inf = int(^uint(0) >> 1)
for l := 3; l <= n; l++ {
for i := 0; i+l-1 < n; i++ {
j := i + l - 1
dp[i][j] = inf
for k := i + 1; k < j; k++ {
score := dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]
if score < dp[i][j] {
dp[i][j] = score
}
}
}
}
return dp[0][n-1]
}class Solution {
public:
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
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][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
}
}
}
return dp[0][n - 1];
}
};class Solution:
def minScoreTriangulation(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(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
return dp[0][n - 1]var minScoreTriangulation = function(values) {
const n = values.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let len = 3; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Number.MAX_SAFE_INTEGER;
for (let k = i + 1; k < j; k++) {
const score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
dp[i][j] = Math.min(dp[i][j], score);
}
}
}
return dp[0][n - 1];
};
Comments