# 每日算法系列【LeetCode 1039】多边形三角剖分的最低得分

+关注继续查看

## 题目描述

输入：
[1,2,3]

6

输入：
[3,7,4,5]

144

输入：
[1,3,1,4,1,5]

13

• 3 <= A.length <= 50
• 1 <= A[i] <= 100

## 代码

### c++

class Solution {
public:
static const int N = 55;
int dp[N][N];
int minScoreTriangulation(vector<int>& A) {
int n = A.size();
memset(dp, 0, sizeof dp);
for (int len = 3; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
int tmp = INT_MAX;
for (int k = i+1; k < j; ++k) {
tmp = min(tmp, A[i]*A[j%n]*A[k%n]+dp[i]
[k%n]+dp[k%n][j%n]);
}
dp[i][j%n] = tmp;
}
}
return dp[0][n-1];
}
};

### python

class Solution:
def minScoreTriangulation(self, A: List[int]) -> int:
n = len(A)
dp = [[0]*n for _ in range(n)]
for l in range(3, n+1):
for i in range(n):
j = i + l - 1
tmp = 0x3f3f3f3f
for k in range(i+1, j):
tmp = min(tmp, A[i]*A[j%n]*A[k%n]+dp[i]
[k%n]+dp[k%n][j%n])
dp[i][j%n] = tmp
return dp[0][n-1]

Inside Java Newscast #1 解读（下）
Inside Java Newscast #1 解读（下）
31 0

29 0
LeetCode（多线程）- 1195. 交替打印字符串
LeetCode（多线程）- 1195. 交替打印字符串
21 0
MYSQL性能调优05_覆盖索引、索引下推、如何选择合适的索引、Order by与Group by优化、索引设计原则（二）
MYSQL性能调优05_覆盖索引、索引下推、如何选择合适的索引、Order by与Group by优化、索引设计原则（二）
44 0

4444 0
217

0