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

题目描述

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

题目解析

1. 多个三角形可以拼接成一个多边形，所以一个凸N边形可分解为两个凸多变形加一个三角形，所以子集的最优解可以合并为全局最优解。
2. 构建dp[i][j] 表示从i～j的三角形最优值，所以dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[I]A[j]A[k]) 其中k∈[i+1, j-1]，可以使用dfs+记忆化搜索，最终返回dp[0][A.size()-1]
3. 记得处理三角形的特殊情况。

C++代码

class Solution {
public:
    
    int dp[105][105];
    int arr[105];

    int dfs(int s, int e) {
        if(e - s <=1) return 0;
        if(dp[s][e] != -1) return dp[s][e];
        int maxTemp = 9999999;
        for(int i = s + 1; i <= e -1; i++) {
            maxTemp = min(maxTemp, dfs(s, i) + dfs(i, e) + arr[s] * arr[i] * arr[e]);
        }
        dp[s][e] = maxTemp;
        return dp[s][e];
    }
    
    int minScoreTriangulation(vector<int>& A) {
        if(A.size() < 4) {
            int ans = 1;
            for(int i = 0; i < A.size(); i++) {
                ans *= A[i];
            }
            return ans;
        }
        for(int i = 0; i < A.size(); i++) {
            arr[i] = A[i];
        }        
        memset(dp, -1, sizeof(dp));
        return dfs(0, A.size() - 1);
    }
};