企业官网建设流程全解析

没有做网站地图影响大吗吗,桐乡城市建设局网站,那里有做像美团的网站的,临汾网站建设题目描述你有一个凸的 n 边形#xff0c;其每个顶点都有一个整数值。给定一个整数数组 values #xff0c;其中 values[i] 是按 顺时针顺序 第 i 个顶点的值。假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形#xff0c;该三角形的值是顶点标记的乘积#xff0c;三角…题目描述你有一个凸的n边形其每个顶点都有一个整数值。给定一个整数数组values其中values[i]是按顺时针顺序第i个顶点的值。假设将多边形剖分为n - 2个三角形。对于每个三角形该三角形的值是顶点标记的乘积三角剖分的分数是进行三角剖分后所有n - 2个三角形的值之和。返回多边形进行三角剖分后可以得到的最低分。示例 1输入values [1,2,3]输出6解释多边形已经三角化唯一三角形的分数为 6。示例 2输入values [3,7,4,5]输出144解释有两种三角剖分可能得分分别为3*7*5 4*5*7 245或 3*4*5 3*4*7 144。最低分数为 144。示例 3输入values [1,3,1,4,1,5]输出13解释最低分数三角剖分的得分情况为 1*1*3 1*1*4 1*1*5 1*1*1 13。提示n values.length3 n 501 values[i] 100解决方案这段代码是基于记忆化递归求解 “多边形三角剖分的最低得分” 问题的完整正确实现核心思路是通过递归拆分多边形为子问题结合记忆化缓存避免重复计算最终得到整个多边形三角剖分的最小得分。核心逻辑核心定义memo二维记忆化数组len×lenmemo[begin][end]缓存顶点区间[begin, end]构成的子多边形三角剖分的最低得分初始值为0xFFFFFF标记 “未计算”dfs(begin, end, s)返回顶点区间[begin, end]三角剖分的最低得分s为顶点值数组传引用避免拷贝。递归边界若begin1end仅 2 个顶点无法构成三角形返回 0无剖分得分是问题的基础边界主函数补充len3返回 0边界防护顶点数不足 3 时无法剖分直接返回 0。记忆化优化递归开始时先检查memo[begin][end]!0xFFFFFF若命中缓存已计算过该区间的最小得分则直接返回缓存值避免重复递归计算将时间复杂度从纯递归的O(2n)降至O(n3)n为顶点数。核心状态转移问题本质枚举分割点ibegin i end将[begin, end]多边形拆分为三个部分左子多边形[begin, i]的剖分得分dfs(begin, i, s)右子多边形[i, end]的剖分得分dfs(i, end, s)当前三角形begin-i-end的得分s[begin] * s[i] * s[end]总得分是三者之和通过min取所有分割点对应的最小得分即为[begin, end]区间的最低剖分得分。主函数逻辑初始化记忆化数组填充0xFFFFFF标记未计算调用dfs(0, len-1, values)计算整个多边形顶点0~len-1的最低剖分得分并返回。关键特点逻辑完整覆盖了边界条件、记忆化缓存、核心得分计算的所有关键环节是该问题的标准记忆化递归解法效率可控记忆化缓存彻底避免重复递归能处理中等规模的顶点数输入实现简洁基于递归框架贴合 “将大问题拆分为子问题” 的动态规划思想易理解、易维护。总结核心思路通过递归枚举所有分割点将大多边形拆分为子多边形 三角形取所有剖分方式的得分最小值结合记忆化缓存优化效率关键设计memo数组是效率核心分割点枚举 子问题递归 得分求和取最小是逻辑核心功能效果能正确计算任意合法顶点数组的多边形三角剖分最低得分结果无偏差。以values [3,7,4,5]为例代码会枚举分割点i1和i2计算所有剖分方式的得分后取最小值 144返回正确结果。函数源码class Solution { public: vectorvectorint memo{}; int dfs(int begin,int end,vectorint s){ int min_x0xFFFFFF; if(begin1end) return 0; if(memo[begin][end]!0xFFFFFF) return memo[begin][end]; for(int ibegin1;iend;i){ min_xmin(min_x,dfs(begin,i,s)dfs(i,end,s)s[begin]*s[i]*s[end]); } memo[begin][end]min_x; return min_x; } int minScoreTriangulation(vectorint values) { int lenvalues.size(); if(len3)return 0; memo.assign(len,vectorint(len,0xFFFFFF)); return dfs(0,len-1,values); } };