题目:多边形三角剖分的最低得分

  • 给定N,想象一个凸N边多边形,其顶点按顺时针顺序依次标记为A[0], A[i], ..., A[N-1]
  • 假设您将多边形剖分为N-2个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有N-2个三角形的值之和。
  • 返回多边形进行三角剖分后可以得到的最低分。
示例 1:
  1. 输入:[1,2,3]
  2. 输出:6
  3. 解释:多边形已经三角化,唯一三角形的分数为 6
示例 2:

image
image

  1. 输入:[3,7,4,5]
  2. 输出:144
  3. 解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,或 3*4*5 + 3*4*7 = 144。最低分数为 144
示例 3:
  1. 输入:[1,3,1,4,1,5]
  2. 输出:13
  3. 解释:最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13
提示:
  • 3 <= A.length <= 50
  • 1 <= A[i] <= 100

来源:力扣(LeetCode)第1039题

链接:https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon

分析:

  • 可以使用dp或者dfs两种方法(好像很多题我都会这么讲。。。)
  • 这两种方式的思路完全一致,唯一的不同就是一个是递归一个是dp。
  • 我们声明两个状态i,j为从第i个位置开始,到第j个位置为止。
  • 我们发现如果i==j-1的话,是不可能会有答案的,因为中间还要有第三个位置。
  • 至少要i+2==j才行,这样中间才能有一个位置放第三个点。
  • 也就是说如果中间有两个位置,那么第三个点就有两种可能,以此类推。
  • 如果中间有多个位置,我们随便选择其中的一个,一个三角形的三个点就是i,j,k(中间的那个点),那么另外n-3个三角形的顶点的值要怎么算呢?我们发现除去i,j,k这个三角形外,其他的三角形的值我们在小一维的dp里已经算过了(就是长度比当前长度小1的那些值)。
  • 比如现在我们要找其他的三角形那么其他的三角形的值就是dp[i][k]和dp[k][j]里面,而这两个值肯定已经算过了,因为这两个值所代表的状态肯定比当前状态的长度要小。

代码:

  • dp

    1. class Solution {
    2. public int minScoreTriangulation(int[] A) {
    3. int len = A.length;
    4. int[][] dp = new int[len][len];
    5. for (int i = 0; i < len; i++) for (int j = 0; j < len; j++) dp[i][j] = Integer.MAX_VALUE;
    6. for (int i = 0; i < len - 1; i++) dp[i][i+1] = 0;
    7. for (int d = 2; d < len; d++) { // 长度
    8. for (int i = 0; i < len - d; i++) {
    9. int j = i + d;
    10. for (int k = i + 1; k < j; k++)
    11. dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
    12. }
    13. }
    14. return dp[0][len-1];
    15. }
    16. }
  • dfs + 记忆化(不加记忆化会超时)

    1. class Solution {
    2. private int[][] memo;
    3. public int minScoreTriangulation(int[] A) {
    4. int len = A.length;
    5. memo = new int[len][len];
    6. return dfs(0, len - 1, A);
    7. }
    8. public int dfs(int left, int right, int[] A) {
    9. if (left + 1 == right) return 0;
    10. if (memo[left][right] != 0) return memo[left][right];
    11. int ans = Integer.MAX_VALUE;
    12. for (int k = left + 1; k < right; k++)
    13. ans = Math.min(ans, dfs(left, k, A) + dfs(k, right, A) + A[left] * A[k] * A[right]);
    14. memo[left][right] = ans;
    15. return ans;
    16. }
    17. }