文章目录一、问题说明二、解题思路一、状态定义二、状态转移方程定义三、初始化四、计算方式三、代码实现四、执行结果五、思考
一、主题说明
以a为顶点0，1，…，n-1的n凸多边形，可以用内部不相交的n-3条对角线将a划分为三角形，如下图所示，是5边形的所有划分方案。 假设凸n边形的边及对角线的长度dij都是给定的正整数，为0ijn-1。 区分后的三角形ijk的权重与其周长相等，求出具有最小值
示例1 :
输入： d=[ 0，2，3，1，5，6 ]，[ 2，0，3，4，8，6 ]，[ 3，3，0，10，13，7 ]，[ 1，4，10，12，12，5 ]
为了应用动态规划，需要将多边形分割得很小。 可以看到，输入的多边形的每一边都属于一个三角形。 把这一边做成一个三角形意味着如上图所示，决定第三个顶点。 找到正确的连接顶点后，多边形的其馀部分将被分成两个小块，这两个块必须进行最佳的三角形分割。 将dp[i][j]从顶点vi
DP [ I ] [ j ]=min (DP [ I ] [ k ] DP [ k ] [ j ] dikkdij ) DP [ I ]=min (DP [ I ] [ k ] DP [ k ] [ j ] d _ { ii )
2 .当定义状态转移方程j - i=1时，有d p [ i ] [ j
] = 0 dp[i][j] = 0 dp[i][j]=0当j - i > 1时，有
d p [ i ] [ j ] = m i n ( d p [ i ] [ k ] + d p [ k ] [ j ] + d i k + d k j + d i j ) , i < k < j dp[i][j] = min(dp[i][k] + dp[k][j] + d_{ik} + d_{kj} + d_{ij}),i < k < j dp[i][j]=min(dp[i][k]+dp[k][j]+dik+dkj+dij),i<k<j
3. 初始化 当j - i = 1时，有 d p [ i ] [ j ] = 0 dp[i][j] = 0 dp[i][j]=0
4. 计算方式 自底向上，自左向右计算dp数组
三、代码实现 /** * 最小三角权剖分 * * @author hh * @date 2021-5-24 23:35 */public class MinWeightTriangulation { public int minWeight(int[][] d){ int[][] dp = new int[d.length][d[0].length]; for(int i = d.length - 1; i >= 0; i--){ for(int j = 0; j < d[0].length; j++){ if(j - i == 1){ dp[i][j] = 0; continue; } dp[i][j] = Integer.MAX_VALUE; for(int k = i + 1; k < j; k++){ dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j] + d[i][k] + d[k][j] + d[i][j]); } } } return dp[0][d[0].length -1]; } public static void main(String[] args){ int[][] d = new int[][]{ {0,2,3,1,5,6}, {2,0,3,4,8,6}, {3,3,0,10,13,7}, {1,4,10,0,12,5}, {5,8,13,12,0,3}, {6,6,7,5,3,0} }; MinWeightTriangulation minWeightTriangulation = new MinWeightTriangulation(); System.out.println(minWeightTriangulation.minWeight(d)); }} 四、执行结果 五、思考 本题和字符串切分、矩阵链乘法的做法非常相似,也是非常经典的，都是对dp数组进行线性划分，读者有时间可以看我的另一篇文章动态规划经典题目-字符串切分、动态规划经典题目-矩阵链乘法，进行举一反三。