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

  • 给定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. }
    9. public int dfs(int left, int right, int[] A) {
    10.     if (left + 1 == right) return 0;
    11.     if (memo[left][right] != 0) return memo[left][right];
    12.     int ans = Integer.MAX_VALUE;
    13.     for (int k = left + 1; k < right; k++)
    14.         ans = Math.min(ans, dfs(left, k, A) + dfs(k, right, A) + A[left] * A[k] * A[right]);
    15.     memo[left][right] = ans;
    16.     return ans;
    17. }
    18. }