?????【区间DP】LeetCode 1039. Minimum Score Triangulation of Polygon

文章目录

• 题意
• 题解
• 代码
• 结果
• 反思
• 参考题解

题意

题解

一个凸 $n$ 边多边形，不停切割下去，最终一定是能切割成 $n-2$ 个三角形。那么按照什么顺序切割才能方便求解呢？

可以发现，一刀下去，两个多边形只有一条边是在内部，其他边都是连续的外围的边，如下图所示：

所以右边的多边形我们可以用 $(i,j)$ 二维状态来表示。

那么继续切割下去，例如切割右边那块多边形，我们应该先把 $(i,j)$ 这条边对应的三角形给找出来，那就是在 $(i,j)$ 之间找到第三个点 $k$ ，如下图所示：

这样右边多边形就被划分为了 3 块，其中除了 $(i,j,k)$ 这个三角形外，两外两块多边形仍然满足只有一条内边的性质，所以可以继续用二位状态表示为 $(i,k)$ 和 $(k,j)$。

那如果不先找三角形 $(i,j,k)$ 会怎么样呢。如下图所示：

这样的话，多边形 $(i,k_1,k_2,j)$ 就会出现两条内边，那么这种多边形就很难用简单的二维状态来表示了，程序中很难实现。

最后就能用二维动态规划来递归求解了。用 $(i,j)$ 表示多边形 $i->i+1->...->j$ ，其中只有 $j->i$ 是内边。设 $dp[i][j]$ 表示多边形 $(i,j)$ 切割后最小得分，那么只需要找到上面所说的切割点 $k$ 就行了，转移方程为：

dp[i][j] = min(dp[i][k] + dp[k][j] + A[i]·A[j]·A[k])

代码

//区间DP问题，难啊难啊难
class Solution {
public:int minScoreTriangulation(vector<int>& A) {int len = A.size();if(len < 3){return 0;}int inf = 0x3fffffff;vector<vector<int> > dp(len+1,vector<int>(len+1,0));//初始化dp数组for(int i=0;i+2<len;i++){dp[i][i+2] = A[i]*A[i+1]*A[i+2];}//枚举长度，根据题目的具体含义，长度需要从2开始for(int l=4;l<=len;l++){//枚举起点for(int i=0;i+l-1<len;i++){   //这样写判断条件就很nice~int j = i+l-1;dp[i][j] = inf;//枚举分割点for(int k=i+1;k<=j-1;k++){dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+A[i]*A[k]*A[j]);}}}return dp[0][len-1];}
};

结果

反思

1. 题解的突破点在于：

   1. 如何去表示一个多边形？（这个太难了，呜呜呜）
   2. 如何考虑一个多边形的所有划分的情况？

2. 主要还是自己没有理解区间DP在思考问题时的路线！区间DP是非常容易看出分解子问题的一类DP问题了，但是我还是没有养成这种分解的好习惯。

3. 对于区间DP问题，它的DP table的含义就是题目中要求的最优值。然后再枚举分割点得到最优值。这是最简单的思路了。

参考题解

1. 每日算法系列【LeetCode 1039】多边形三角剖分的最低得分