LeetCode 1547. 切棍子的最小成本 Java版本

棍子的最小成本 Java版本"/>

LeetCode 1547. 切棍子的最小成本 Java版本

1547. 切棍子的最小成本

难度困难

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

示例 1：

输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。

示例 2：

输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4，6，5，2，1] 的总成本 = 22，是所有可能方案中成本最小的。

提示：

• 2 <= n <= 10^6
• 1 <= cuts.length <= min(n - 1, 100)
• 1 <= cuts[i] <= n - 1
• cuts 数组中的所有整数都 互不相同

题解

用了区间dp，构建一个二维数组dp，其中
d p [ i ] [ j ] 表 示 从 第 i 个 分 块 到 第 j 个 分 块 的 最 小 花 费 dp[i][j]表示从第i个分块到第j个分块的最小花费 dp[i][j]表示从第i个分块到第j个分块的最小花费
状态转移方程为
d p [ i ] [ j ] = M i n ( d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + l e n g t h i j ) 其 中 i < = k < = j dp[i][j] = Min(dp[i][k]+dp[k+1][j]+length_{ij} )其中i<=k<=j dp[i][j]=Min(dp[i][k]+dp[k+1][j]+lengthij​)其中i<=k<=j

l e n g t h i j 代 表 从 i 到 j 的 长 度 length_{ij}代表从i到j的长度 lengthij​代表从i到j的长度

java代码如下，只有函数

 public  int minCost(int n, int[] cuts) {//先把切开的位置排序Arrays.sort(cuts);//根据切开的位置把棍子分为cuts.length + 1块，每块长度记录在slices数组中//因为数组下标从0开始int[] slices = new int[cuts.length + 2];slices[0] = 0;slices[1] = cuts[0];for (int i = 2; i < cuts.length + 1; i++) {slices[i] = (cuts[i - 1] - cuts[i - 2]);}slices[cuts.length + 1] = n - cuts[cuts.length - 1];//sliceCount为slices数组长度，等于总块数+1int sliceCount = slices.length;//二维dp数组，dp[from][to]表示从from分块到to分块的miniCostint[][] dp = new int[sliceCount][sliceCount];for (int i = 0; i < sliceCount; i++) {for (int j = 0; j < sliceCount; j++) {dp[i][j] = 10000001;//对dp赋初值}}//i为from到to分块之间的块的个数（间隔）从0到总块数-1（sliceCount-2)for (int i = 0; i < sliceCount - 1; i++) {for (int j = 1; j < sliceCount; j++) {if (i + j >= sliceCount) {break;}//从自身到自身 花费为0if (i == 0) {dp[j][i + j] = 0;} else {int temp = 10000001;//从第j块到j+i块的棍子长度int s = 0;for(int k=j;k<=i+j;k++){s+=slices[k];}for (int k = j; k < i + j; k++) {//状态转移方程dp[j][i + j] = Math.min(dp[j][k] + dp[k + 1][i + j] + s, temp);temp = dp[j][i + j];}}}}return dp[1][sliceCount - 1];}