用C++代码解决问题 【问题描述】使用动态规划算法解凸多边形最优三角剖分问题，具体来说就是，依据递归式，按照顺序求得子问题，使得该三角剖分中诸三角形上权之和为最小。 【输入形式】在屏幕上输入凸多边形顶点个数和顶点坐标。按逆时针顺序输入顶点坐标。 【输出形式】输出最优三角形的个数 【样例输入】 7 8 26 0 20 0 10 10 0 22 12 27 21 15 26 【样例输出】 5

以下是 C++ 代码实现：

#include<bits/stdc++.h>
using namespace std;
int n;
double x[105],y[105],dp[105][105];
double dis(int i,int j,int k){ //计算三角形面积
    return fabs((x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]));
}
double solve(int l,int r){ //递归求解
    if(dp[l][r])return dp[l][r];
    if(r-l==1)return 0;
    double res=1e18;
    for(int i=l+1;i<r;i++){
        res=min(res,solve(l,i)+solve(i,r)+dis(l,i,r));
    }
    return dp[l][r]=res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    printf("%d\n",(int)(solve(1,n)/1000+0.5)); //四舍五入取整
    return 0;
}

思路解析：

本题使用动态规划求解凸多边形的最优三角剖分问题，递归求解子问题，最后得到最优解。

具体实现：

1.定义 $dp$ 数组，其中 $dp_{i,j}$ 表示顶点 $i$ 到 $j$ 构成的子多边形的最优三角剖分的权值和。

2.使用 $solve(l,r)$ 函数递归求解子问题，其中 $l$ 和 $r$ 分别表示子多边形的左右端点，递归终止条件为 $r-l=1$。

3.在 $solve(l,r)$ 函数中，枚举 $i \in (l+1,r-1)$，将子问题划分为两个部分，即 $solve(l,i)$ 和 $solve(i,r)$，再加上三角形 $(l,i,r)$ 的权值，即 $dis(l,i,r)$，求最小值，即可得到 $dp_{l,r}$。

4.最终答案即为 $dp_{1,n}$，将其除以 $1000$ 并四舍五入取整即可得到最优三角形的个数。

时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。