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

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

题目描述

给定 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。

提示

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

题解

一个凸  边多边形,不停切割下去,最终一定是能切割成  个三角形。那么按照什么顺序切割才能方便求解呢?

可以发现,一刀下去,两个多边形只有一条边是在内部,其他边都是连续的外围的边,如下图所示:

所以右边的多边形我们可以用  二维状态来表示。

那么继续切割下去,例如切割左边那块多边形,我们应该先把  这条边对应的三角形给找出来,那就是在  之间找到第三个点  ,如下图所示:

这样右边多边形就被划分为了 3 块,其中除了  这个三角形外,两外两块多边形仍然满足只有一条内边的性质,所以可以继续用二位状态表示为  和 。

那如果不先找三角形  会怎么样呢。如下图所示:

这样的话,多边形  就会出现两条内边,那么这种多边形就很难用简单的二维状态来表示了,程序中很难实现。

最后就能用二维动态规划来递归求解了。用  表示多边形  ,其中只有  是内边。设  表示多边形  切割后最小得分,那么只需要找到上面所说的切割点  就行了,转移方程为:

代码

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]
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
13天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
24 2
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
60 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
79 0
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
42 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
39 0