1039 多边形三角剖分的最低得分（状态机DP）（灵神笔记）

本文主要是介绍1039 多边形三角剖分的最低得分（状态机DP）（灵神笔记），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

多边形三角剖分的最低得分
你有一个凸的 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 {private int[] values;private int[][] cache;public int minScoreTriangulation(int[] values) {this.values = values;int n = values.length;cache = new int[n][n];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}return dfs(0, n - 1);}//dfs表示顶点i到顶点j这个多边形的最低得分private int dfs(int i, int j) {if (i + 1 == j) {return 0; //只有两个点，无法构成三角形}if (cache[i][j] != -1) {return cache[i][j];}int ans = Integer.MAX_VALUE;for (int k = i + 1; k < j; k++) {ans = Math.min(ans, dfs(i, k) + values[i] * values[j] * values[k] + dfs(k, j));}return cache[i][j] = ans;}
}

递推

class Solution {public int minScoreTriangulation(int[] values) {int n = values.length;int[][] f = new int[n][n];for (int i = n - 3; i >= 0; i--) {//i<k 倒序枚举 j>i+1for (int j = i + 2; j < n; j++) {//k<j 正序枚举f[i][j] = Integer.MAX_VALUE;for (int k = i + 1; k < j; k++) {f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + values[i] * values[j] * values[k]);}}}return f[0][n - 1];}
}