1039. 多边形三角剖分的最低得分

Problem: 1039. 多边形三角剖分的最低得分

思路

对于多边形三角剖分的最低得分问题，我们可以使用动态规划来解决。首先，将问题分解为更小的子问题：选择一个顶点作为三角形的一个顶点，然后计算剩下的两个顶点形成的所有可能三角形的得分，并递归地计算剩余部分的最低得分。最终的答案将是所有可能的选择中最低的得分。
具体而言，我们可以通过以下两种方式实现：
记忆化搜索：使用一个二维数组dp存储已计算过的子问题答案，避免重复计算。
严格位置依赖的动态规划：按照从大到小的顺序计算并填充dp数组，利用已计算的结果计算更大的子问题。

解题方法

记忆化搜索：定义函数f用于计算arr[l]和arr[r]之间的最低得分，其中dp[l][r]用于存储结果，避免重复计算。
严格位置依赖的动态规划：从多边形的较小部分开始计算，逐步构建到整个多边形的最低得分。

复杂度

时间复杂度:

$O(n3)$，其中nn是多边形的顶点数。这是因为我们需要遍历所有可能的三角形组合。

空间复杂度:

$O(n2)$，主要由dp数组的大小决定。

Code

class Solution {
    // 记忆化搜索
    public int minScoreTriangulation1(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }
        return f(arr, 0, n - 1, dp);
    }

    public int f(int[] arr, int l, int r, int[][] dp) {
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        int ans = Integer.MAX_VALUE;
        if (l == r || l + 1 == r) {
            ans = 0;
        } else {
            for (int m = l + 1; m < r; m++) {
                ans = Math.min(ans, f(arr, l, m, dp) + f(arr, m, r, dp) + arr[l] * arr[m] * arr[r]);
            }
        }
        if (dp[l][r] == -1) {
            dp[l][r] = ans;
        }
        return ans;
    }

    // 严格位置依赖的动态规划
    public int minScoreTriangulation(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        // 初始化为0 可以不初始化
        for (int l = n - 3; l >= 0; l--) {
            for (int r = l + 2; r < n; r++) {
                dp[l][r] = Integer.MAX_VALUE;
                for (int m = l + 1; m < r; m++) {
                    dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m][r] + arr[l] * arr[m] * arr[r]);
                }
            }
        }
        return dp[0][n - 1];
    }
}