【lambda表达式】【DP】个人练习-Leetcode-1039. Minimum Score Triangulation of Polygon

题目链接:https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/

题目大意:给出一个凸多边形,每个顶点有一个值values[i],顶点按照顺时针给出。将其三角化,每个三角形的值是三个顶点值的乘积,一个三角化方法的值是所有三角形的值的和。求三角化方法最低取得的值。

思路:凸多边形三角化上一次碰到还是卡塔兰数(凸多边形三角化的方案数就是卡塔兰数)。但具体记不太清了。先想着的是一共有3n-6个数,其中n个数必然是凸多边形的顶点。剩下的2n-6个数是重复一遍的,也就是n-3个数。但怎么算最终值有点没想出来。

看了题解后,知道了可以dp来做,就是分割任务。对一条凸多边形的边i-j来说,最终的最优值就是i-j-k(三角形)+ i-k(凸多边形)+ k-j(凸多边形)。两个凸多边形可以递归。

但我把递归的dfs函数写在外面时,就超时了,只有和题解一样用lambda表达式写dfs函数才能通过。应该是lambda表达式函数调用开销小,局部性更好吧。

关于lambda表达式的递归,这篇文章很详细:https://blog.csdn.net/J__M__C/article/details/125437699

完整代码

class Solution {
public:int minScoreTriangulation(vector<int>& v) {int n = v.size();vector<vector<int>> dp(n, vector<int>(n, -1)); auto dfs = [&](auto&& self, int i, int j) -> int {if (i + 1 == j)return 0; int &res = dp[i][j];if (res != -1) return res;res = INT_MAX;for (int k = i + 1; k < j; k++) {res = min(res, self(self, i, k) + self(self, k, j) + v[i] * v[j] * v[k]);}return res;};return dfs(dfs, 0, n - 1);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/9569.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

沙龙活动精彩回顾:攸信携手博格咨询,探索数智管理的奥秘

10月30日&#xff0c;一场聚焦数智管理的沙龙活动在热烈的氛围中圆满落幕。本次活动由攸信携手博格咨询共同举办&#xff0c;有幸邀请到了资深讲师书麟老师、攸信项目经理黄小容以及市场部经理高建成&#xff0c;他们共同为参会者带来了一场关于数智管理的知识盛宴。 01深入剖析…

17个工作必备的Python自动化代码

Python是一种流行的编程语言&#xff0c;以其简单性和可读性而闻名。因其能够提供大量的库和模块&#xff0c;它成为了自动化各种任务的绝佳选择。让我们进入自动化的世界&#xff0c;探索17个可以简化工作并节省时间精力的Python脚本。 1.自动化文件管理 1.1 对目录中的文件…

【IEEE/EI会议】第八届先进电子材料、计算机与软件工程国际学术会议(AEMCSE 2025)

会议通知 会议时间&#xff1a;2025年4月25-27日 会议地点&#xff1a;中国南京 会议官网&#xff1a;www.aemcse.org 会议简介 第八届先进电子材料、计算机与软件工程国际学术会议&#xff08;AEMCSE 2025&#xff09;由南京信息工程大学主办&#xff0c;将于2025年4月25日…

AndroidStudio-文本显示

一、设置文本的内容 1.方式&#xff1a; &#xff08;1&#xff09;在XML文件中通过属性&#xff1a;android:text设置文本 例如&#xff1a; <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.andr…

关于CountDownLatch失效问题

一、项目背景 这几天要开发一个类似支付宝那种年度账单统计的功能&#xff0c;就是到元旦后支付完会把用户这一年的消费情况从各个维度&#xff08;我们把这一个维度称作一个指标&#xff09;统计分析形成一张报告展示给用户。 这个功能实现用到了CountDownLatch。假如统计分析…

【含开题报告+文档+源码】基于SSM的物流管理系统设计与实现

开题报告 随着电子商务的迅猛发展和人们生活水平的提高&#xff0c;快递服务行业正经历着前所未有的增长。占航快递公司作为国内知名的快递企业之一&#xff0c;面临着巨大的机遇和挑战。传统的快递服务管理方式已经无法满足日益增长的业务需求&#xff0c;快递服务流程中的问…

【AtCoder】Beginner Contest 377-C.Avoid Knight Attack

Avoid Knight Attack 题目链接 Problem Statement There is a grid of N 2 N^2 N2 squares with N N N rows and N N N columns. Let ( i , j ) (i,j) (i,j) denote the square at the i i i-th row from the top ( 1 ≤ i ≤ N ) (1\leq i\leq N) (1≤i≤N) and j j…

sizeof和strlen区分,(好多例子)

sizeof算字节大小 带\0 strlen算字符串长度 \0之前

Javascript中如何实现函数缓存?函数缓存有哪些应用场景?

#一、是什么 函数缓存&#xff0c;就是将函数运算过的结果进行缓存 本质上就是用空间&#xff08;缓存存储&#xff09;换时间&#xff08;计算过程&#xff09; 常用于缓存数据计算结果和缓存对象 解释 const add (a,b) > ab; const calc memoize(add); // 函数缓存…

MATLAB实现智能水滴算法(Intelligent Water Drops Algorithm, IWDA)

1.智能水滴算法介绍 智能水滴算法&#xff08;Intelligent Water Drops Algorithm&#xff0c;IWDA&#xff09;是一种基于水滴特性的智能优化算法&#xff0c;它借鉴了水滴在自然界中的运动和形态变化规律&#xff0c;通过模拟水滴的形成、发展和消亡过程&#xff0c;实现问题…

(Go基础)Go的运行流程步骤与包的概念

1. 快速入门 所有的go开发&#xff0c;都必须存在并包含在某一个包内 .go 是go语言程序的后缀名 1.1 编译 通过使用 go build 命令对该go文件进行编译&#xff0c;生成.exe文件 1.2 运行 运行刚刚生成出来的test.exe文件既可&#xff0c;不过并不不是双击&#xff0c;而是在…

AI 写作(三)文本生成算法:创新与突破(3/10)

一、生成式与判别式模型&#xff1a;AI 写作的基石 &#xff08;一&#xff09;区别与特点 生成式模型和判别式模型在多个方面存在明显差异。在优化准则上&#xff0c;生成式模型致力于学习联合概率分布&#xff0c;而判别式模型则专注于建立输入数据和输出之间的关系&#xf…

ubuntu下使用pocketsphinx进行语音识别(包含交叉编译)

文章目录 前言一、pocketsphinx的介绍二、ubuntu下编译三、使用示例1.模型选择2.代码示例3.自定义字典 四、交叉编译总结 前言 由于工作需要语音识别的功能&#xff0c;环境是在linux arm版上&#xff0c;所以想先在ubuntu上跑起来看一看&#xff0c;就找了一下语音识别的开源…

中国自主品牌荣耀时刻:海豹荣获欧洲车身大奖

近日&#xff0c;在德国巴特瑙海姆举行的2024欧洲车身大会上&#xff0c;比亚迪海豹凭借其卓越的车身架构设计、创新技术和美学设计&#xff0c;一举斩获了本次大赛第三名的殊荣。 这不仅是中国自主品牌在欧洲车身大会上的首次获奖&#xff0c;而且也是比亚迪技术创新与实力在国…

RocketMQ 广播消息

所谓的广播消息就是发送的一条消息会被多个消费者收到。 ⼴播是向主题&#xff08; topic &#xff09;的所有订阅者发送消息。订阅同⼀个 topic 的多个消费者&#xff0c;能全量收到⽣产者发送的所有消息。 生产者发送了10个order&#xff0c;每个order里面有5个消息&#xff…

如何实现智慧园区的节能降耗?

江园科技智慧园区实现智慧园区节能降耗可以从以下几个方面入手&#xff1a; 能源监测与管理系统 - 安装智能电表、水表和气表等设备&#xff0c;实时精准地监测园区内各区域、各企业及各设备的能源消耗情况&#xff0c;如电量的峰谷时段使用量、用水量的波动等。这些数据会传输…

索引【MySQL】

文章目录 聚簇索引 VS 非聚簇索引索引MySQL与磁盘交互的基本单位主键索引索引操作唯一索引的创建普通索引的创建复合索引 索引创建原则 聚簇索引 VS 非聚簇索引 MyISAM存储引擎 - 主键索引结构 MyISAM存储引擎同样采用B树作为索引的基本数据结构 与InnoDB存储引擎的B树不同的…

CDH大数据平台部署

二、CDH简介 全称Cloudera’s Distribution Including Apache Hadoop。 hadoop的版本 (Apache、CDH、Hotonworks版本) 在公司中一般使用cdh多一些&#xff08;收费的&#xff09;、也有公司使用阿里云大数据平台、微软的大数据平台。 国内也有一些平台&#xff1a;星环大数…

如何删除苹果手机所有照片:彻底清理指南

随着时间的推移&#xff0c;我们的iPhone往往会积累大量照片&#xff0c;这些照片占据了大量存储空间并可能影响设备性能。有时&#xff0c;为了快速释放空间或重置手机内容&#xff0c;您可能需要了解如何删除苹果手机所有照片。别担心&#xff0c;本文将向你讲解如何删除苹果…

JAVA开源项目 服装销售平台 计算机毕业设计

博主说明&#xff1a;本文项目编号 T 054 &#xff0c;文末自助获取源码 \color{red}{T054&#xff0c;文末自助获取源码} T054&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…