当前位置: 首页 > news >正文

lc1039-多边形三角剖分的最低得分

题目描述

  • 有一个凸的 n 边形,其每个顶点都有一个整数值
  • 将其剖分为 n-2 个三角形
  • 每个三角形的值都是其三个顶点值的乘积
  • 返回剖分后可以得到的最低分

示例

1039-example-02

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

题解

  • 思路
    • 是道经典题,但若是第一次见,那就是“寄”
    • 固定一边,比如 "i<->j",三角形的第三个顶点为 i+1, i+2, ..., j-1 中的某一点
    • 若三角形固定,则其左右(若有)必有最小值,递归地求就行
    • "i,j" 是 n^2 的循环,k 从 i+1, ..., j-1 是 n,所以时间复杂度为 O(n^3)
    • 怎么想到的?我也想问~
func minScoreTriangulation(values []int) int {n := len(values)f := make([][]int, n)for i := 0; i < n; i ++ { f[i] = make([]int, n) }for size := 3; size <= n; size ++ {for i := 0; i + size - 1 < n; i ++ {j := i + size - 1;if size == 3 {f[i][j] = values[i] * values[i + 1] * values[j]} else {f[i][j] = 1e9for k := i + 1; k < j; k ++ {f[i][j] = min(f[i][j], f[i][k] + f[k][j] +values[i] * values[j] * values[k])}}}}return f[0][n - 1]
}
http://www.hskmm.com/?act=detail&tid=20346

相关文章:

  • Powershell 进阶语(三)
  • 随机函数
  • 集合进阶-collection集合
  • 115. 不同的子序列
  • 素数定理的初等证明
  • Spring Boot项目中集成MyBatis-Plus
  • 深入解析:ShellExtensionU.dll COMToolKit.dll CardRes.dll grubinst.exe vbar332.dll Vb5db.dll dao360.dll
  • 我不懂 愈完美愈是空洞 挂着张可憎面容 维系虚假脆弱的梦
  • 51c自动驾驶~合集33 - 详解
  • VSCod安装esp-idf插件 ERROR_INVALID_PIP错误解决
  • 一款在线免费 PDF AI 工具平台,PDF 拆分,合并,加水印,PDF与Word、Excel、PPT、图片、TXT、HTML、Markdown互转的在线AI工具
  • 计算机核心课
  • 【SimpleFOC】vofa+监控电机数据
  • ubuntu虚拟机磁盘扩展
  • 数学知识
  • The 3rd Universal Cup. Stage 23: Hong Kong
  • 从0到1搭建高隐蔽性C2基础设施
  • RESTful风格
  • 软工9.27
  • 一些积分的题解
  • 2025 年超声波清洗机最新权威推荐排行榜:龙门式 / 悬挂式 / 全自动等多类型设备 TOP3 品牌深度解析与选购指南
  • 问题总结,软工9.28
  • 数据类型-字符串
  • 在AI技术唾手可得的时代,挖掘新需求成为制胜关键——某知名益智游戏框架需求探索
  • 详细介绍:零基础学AI大模型之LangChain六大核心模块与大模型IO交互链路
  • 基础组合计数与卢卡斯定理
  • 2025 最新中国过滤器品牌 TOP10 权威测评推荐厂家与选购指南
  • 2025 年东莞物流公司 TOP 物流服务推荐排行榜,东莞货运物流,东莞到全国物流,东莞大型设备物流,东莞到越南物流专线东莞大件物流,东莞整车物流公司推荐!
  • 使用Python网络爬虫抓取牛客网题目
  • 题解:洛谷 P1012 [NOIP 1998 提高组] 拼数