原文链接: https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon

英文原文

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 (i.e., clockwise order).

You will triangulate the polygon into n - 2 triangles. For each triangle, the value of that triangle is the product of the values of its vertices, and the total score of the triangulation is the sum of these values over all n - 2 triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of the polygon.

 

Example 1:

Input: values = [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

Input: values = [3,7,4,5]
Output: 144
Explanation: 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 is 144.

Example 3:

Input: values = [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

 

Constraints:

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

中文题目

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。
 

示例 1：

输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。

示例 3：

输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。

 

提示：

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

通过代码

高赞题解

解题思路

dp[i][j]表示从i到j序列的最低分。记底边为ij的三角形顶点为m，三角形imj将多边形分成三部分，总分即为三部分的分数和（如果m=i+1或m=j-1，则对应第一或第三部分分数为0）。
那么m在什么位置分数最低呢，将m从i+1到j-1遍历，分别计算dp[i][m]+A[i]*A[j]*A[m]+dp[m][j],取其中最小值即为dp[i][j]。
dp[i][j]=min(dp[i][m]+A[i]*A[j]*A[m]+dp[m][j]),for m in range [i+1,j-1]

dp table只用到右上半部分，初始化相邻两元素序列结果为0（两元素序列不能构成三角形）；采用自底向上、自左向右的方向计算dp table（也可以选择别的遍历顺序，只要保证从左下往右上就行了）。最终输出dp[0][n-1]。

新手小白的介绍和代码希望大家多提意见。

代码

class Solution {                                                                                                                                                                                               
public:
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
	int **dp = new int*[n];
	for (int i = 0; i < n; i++)  dp[i] = new int[n]();//初始化全0
        
        for (int i = n-3; i >= 0; i--) {
            for (int j = i + 2; j < n;j++) {
                for (int m = i + 1; m < j; m++) {
                    if(dp[i][j]==0) 
                        dp[i][j]= A[i] * A[j] * A[m] + dp[i][m] + dp[m][j];
                    else 
                        dp[i][j] = min(dp[i][j],A[i] * A[j] * A[m] + dp[i][m] + dp[m][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

统计信息

通过次数	提交次数	AC比率
4714	8460	55.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言