C++ 实现 力扣1039. 多边形三角剖分的最低得分_三角剖分 自相交

力扣1039. 多边形三角剖分的最低得分
动态规划问题
建立动态规划方程的过程：
opt( l, r ) 表示从顶点i到j的最优（最低）分数
ij距离为1时分数是0（这里一直没搞清楚所以方程一直建不起来）
然后就是普通的动态规划的思路了
比如opt(0,3)
分解为以下两个式子最小值

opt(0,1) +opt(1,3)+weight(013)
opt(0,2) +opt(2,3)+weight(023)
1
2

也就是K遍历每一个[l+1, r) 的最小值

//凸多边形最优三角剖分
#include<bits/stdc++.h> //万能头文件，包含了目前C++所包含的所有头文件
using namespace std;

int main(){
    vector<int> values={3,7,4,5};
    int n=values.size();
    vector<vector<int>>dp(n,vector<int>(n,INT_MAX));
    for(int l=0; l<n-1; l++)
        dp[l][l+1]=0;
    for(int len=2; len<n; len++)
        for (int l=0; l<n-len; l++){
            int r=l+len;
            int min=INT_MAX ;
            for(int k=l+1; k<r; k++){
                int weight = dp[l][k]+dp[k][r]+values[l]*values[r]*values[k];
                min=min<weight?min:weight;
            }
            dp[l][r]=min;
        }
    cout<<dp[0][n-1];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23