试题出自试卷《（软设）第一次阶段测试【2024年上半年】》

阅读下列说明和代码，回答问题1和问题2，将解答写在答题纸的对应栏内。
【说明】
凸多边形是指多边形的任意两点的连线均落在多边形的边界或内部。相邻的点连线落在多边形边界上，称为边；不相邻的点连线落在多边形内部，称为弦。假设任意两点连线上均有权重，凸多边形最优三角剖分问题定义为：求将凸多边形划分为不相交的三角形集合，且各三角形权重之和最小的剖分方案。每个三角形的权重为三条边权重之和。
假设N个点的凸多边形点编号为V₁,V₂,……,V_N,若在V_K处将原凸多边形划分为一个三角形V₁V_kV_N，两个子多边形V₁,V₂,…,V_k和V_k,V_k+1,…V_N，得到一个最优的剖分方案，则该最优剖分方案应该包含这两个子凸边形的最优剖分方案。用m[i][j]表示带你V_i-1,V_i,…V_j构成的凸多边形的最优剖分方案的权重，S[i][j]记录剖分该凸多边形的k值。
则

其中：W(V_i-1V_kV_j)=W_i-1,k＋W_k,j＋W_j,i-1为三角形V_i-1V_kV_j的权重，W_i-1,k，W_k,j，W_j,i-1分别为该三角形三条边的权重。求解凸多边形的最优剖分方案，即求解最小剖分的权重及对应的三角形集。
[C代码]
＃include＜stdio.h＞
＃define N 6 //凸多边形规模
int m[N＋1] [N＋1]; //m[i][j]表示多边形V_i-1到V_j最优三角剖分的权值
int S[N＋1] [N＋1]; //S[i][j]记录多边形V_i-1到V_j最优三角剖分的k值
int W[N＋1] [N＋1]; //凸多边形的权重矩阵，在main函数中输入
/*三角形的权重a，b，c，三角形的顶点下标*/
int get_ triangle_weight（int a，int b，int c）

{
     return W[a][b]＋W[b][c]＋W[c][a];
}
/*求解最优值*/
void triangle_partition(){
int i,r,k,j;
int temp;
/*初始化*/
for(i=1;i<=N;i++){
m[i][i]=0;
}
/*自底向上计算m，S*/
for(r=2;（1）;r++)

{     /*r为子问题规模*/
       for(i=1;i<=N-r+1;i++)

     {
        （2）;
         m[i][j]= m[i][i]+m[i+1][j]+get_triangle_weight(i-1,i,j); /*k=i*/
         S[i][j]=i;
         for(k=j+1;k<j;k++)

          {     /*计算 [i][j]的最小代价*/
                 temp=m[i][k]+m[k+1][j]+ge_triangle_ weight(i-1,k,j);
                if((3))

                   {         /*判断是否最小值*/ 
                               m[i][j]=temp;
                               S[i][j]=k;
                   }
          }
     }
}
}
/*输出剖分的三角形i，j：凸多边形的起始点下标*/
void print_triangle(int i,int j){
if(i==j) return;
print_triangle(i,S[i][j]);
print_ triangle((4));
print(“V%d- -V%d- -V%d\n“,i-1,S[i][j],j);
}

【问题1】（8分）
根据题干说明，填充C代码中的空（1）~（4）。
【问题2】（7分）
根据题干说明和C代码，该算法采用的设计策略为（5）。
算法的时间复杂度为（6），空间复杂度为（7）（用O表示）