重庆建设厅网站首页,国家高新技术企业认定有什么用,网站增加导航栏,网站建设肆金手指排名8#x1f34e;作者简介#xff1a;硕风和炜#xff0c;CSDN-Java领域新星创作者#x1f3c6;#xff0c;保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享#x1f48e;#x1f48e;#x1f48e; #x1f34e;座右… 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 座右铭人生如棋我愿为卒行动虽慢可谁曾见我后退一步 目录题目链接题目描述求解思路实现代码运行结果暴力递归求解思路实现代码运行结果记忆化搜索求解思路实现代码运行结果动态规划求解思路实现代码运行结果共勉题目链接
1039. 多边形三角剖分的最低得分
题目描述
你有一个凸的 n 边形其每个顶点都有一个整数值。给定一个整数数组 values 其中 values[i] 是第 i 个顶点的值即顺时针顺序。
假设将多边形剖分为 n - 2 个三角形。对于每个三角形该三角形的值是顶点标记的乘积三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分 。
示例 1
输入values [1,2,3] 输出6 解释多边形已经三角化唯一三角形的分数为 6。 示例 2 输入values [3,7,4,5] 输出144 解释有两种三角剖分可能得分分别为375 457 245或 345 347 144。最低分数为 144。
示例 3 输入values [1,3,1,4,1,5] 输出13 解释最低分数三角剖分的得分情况为 113 114 115 111 13。
提示
n values.length 3 n 50 1 values[i] 100
求解思路实现代码运行结果
暴力递归
求解思路
为了能够让同学们更好的理解这个过程我特意将整个思考的过程以及作图的过程都绘制在下面这张图中希望可以通过下面这张图更好的帮助你理解整个过程大家可以结合这张图来理解整个题目的求解思路。 实现代码
注意代码的实现方式可以有很多大家根据自己的习惯来就好
class Solution {public int minScoreTriangulation(int[] values) {int n values.length;return dfs(0, n - 1,values);}private int dfs(int left, int right,int[] values) {if (left 1 right) return 0;int min Integer.MAX_VALUE;for (int k left1; k right; k){min Math.min(min, dfs(left, k,values) dfs(k, right,values) values[left] * values[right] * values[k]);}return min;}
}运行结果
大家不要看到时间超限就害怕相反看到这个我们更应该放心使我们期待的结果。 记忆化搜索
求解思路
核心思路就是我们上面的求解过程如果没有理解可以继续看上面的图解过程。在原来的基础上加缓存表将结果进行记录避免重复计算。
实现代码
class Solution {public int minScoreTriangulation(int[] values) {int n values.length;int[][] dpnew int[n][n];for(int i0;in;i) Arrays.fill(dp[i],-1);return dfs(0, n - 1,values,dp);}private int dfs(int left, int right,int[] values,int[][] dp) {if (left 1 right) return dp[left][right]0;if(dp[left][right]!-1) return dp[left][right];int min Integer.MAX_VALUE;for (int k left1; k right; k){min Math.min(min, dfs(left, k,values,dp) dfs(k, right,values,dp) values[left] * values[right] * values[k]);}return dp[left][right]min;}
}运行结果
加个缓存表就是香通过 动态规划
求解思路
同理核心求解思路我们上面已经讲过了此处不同的是原来通过递归此时我们通过dp数组和循环即可完成。
实现代码
继续改进
class Solution {public int minScoreTriangulation(int[] values) {int n values.length;int[][] dpnew int[n][n];for(int leftn-3;left0;left--){for(int rightleft2;rightn;right){int min Integer.MAX_VALUE;for (int k left1; k right; k){min Math.min(min, dp[left][k] dp[k][right] values[left] * values[right] * values[k]);}dp[left][right]min;}}return dp[0][n - 1];}
}
}运行结果 共勉
最后我想送给大家一句一直激励我的座右铭希望可以与大家共勉
