开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介: 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。 假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。 返回多边形进行三角剖分后可以得到的最低分。
+关注继续查看

题目描述


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

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

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

示例1

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

示例2

image.png

输入:
[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

题解



image.png

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

image.png


image.png

image.png


image.png

image.png


image.png

代码


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]

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Inside Java Newscast #1 解读(下)
Inside Java Newscast #1 解读(下)
31 0
每日算法系列【LeetCode 810】黑板异或游戏
一个黑板上写着一个非负整数数组 nums[i] 。小红和小明轮流从黑板上擦掉一个数字,小红先手。如果擦除一个数字后,剩余的所有数字按位异或运算得出的结果等于 0 的话,当前玩家游戏失败。 (另外,如果只剩一个数字,按位异或运算得到它本身;如果无数字剩余,按位异或运算结果为 0。) 换种说法就是,轮到某个玩家时,如果当前黑板上所有数字按位异或运算结果等于 0,这个玩家获胜。 假设两个玩家每步都使用最优解,当且仅当小红获胜时返回 true。 示例1
29 0
LeetCode(多线程)- 1195. 交替打印字符串
LeetCode(多线程)- 1195. 交替打印字符串
21 0
MYSQL性能调优05_覆盖索引、索引下推、如何选择合适的索引、Order by与Group by优化、索引设计原则(二)
MYSQL性能调优05_覆盖索引、索引下推、如何选择合适的索引、Order by与Group by优化、索引设计原则(二)
44 0
直击 KubeCon 现场 | 阿里云 Hands-on Workshop 亮点回顾
相关文章链接【合集】规模化落地云原生,阿里云亮相 KubeCon China沉淀九年,一文看清阿里云原生大事件 2019 年 6 月 24 日至 26 日,KubeCon + CloudNativeCon + Open Source Summit(上海 )在中国上海盛装启幕。
4444 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载