【区间 dp】A028

区间 dp】A028"/>

【区间 dp】A028

一、Problem

切棍子的最小成本

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

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

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

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

返回切棍子的 最小总成本

输入：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）

二、Solution

可惜的是这题没做出来，感觉不是很难，因为我们不知道按什么顺序切割是最优的方案，所以突破点是穷举所有切割点

方法一：区间 dp

• 定义状态：
  • f[i][j] 表示用 cuts 的某种顺序切割 [i, j] 这一段可以需要最小代价
• 思考初始化：
  • f[…][…] = -1；f[i][i/i+1] = 0 表示切割长度为 0/1 的木棍不用切割
• 思考状态转移方程：
  • f[i][j] = f[i][k] + f[k][j] + cuts[j] - cuts[i]
• 思考输出：f[0][n]

由于这里可能会切割到第 0 个位置和最后一个位置，故把 cuts 数组增加两个元素 [0, n]

细节一大堆…

class Solution {public int minCost(int n, int[] Cuts) {Arrays.sort(Cuts);int sz=Cuts.length, cuts[] = new int[sz+2], m=cuts.length, INF=0x3f3f3f3f, f[][] = new int[m+5][m+5];System.arraycopy(Cuts, 0, cuts, 1, sz); cuts[m-1]=n;for (int i=0; i<m; i++) Arrays.fill(f[i], INF);for (int i=1; i<m; i++) f[i][i]=f[i-1][i]=0;for (int len=1; len<=n; len++)   for (int l=0; l<m-len; l++) {int r=l+len;for (int k=l; k<r; k++) {f[l][r] = Math.min(f[l][r], f[l][k]+f[k][r]+cuts[r]-cuts[l]);}}return f[0][m-1];}
}

随便改了一下，记忆化版本

class Solution {int sz, cuts[], m, INF, f[][];int dfs(int l, int r) {if (r-l<=1) return 0;if (f[l][r] != INF) return f[l][r];int ans=INF;for (int i=l+1; i<r; i++) {ans = Math.min(ans, dfs(l, i)+dfs(i, r)+cuts[r]-cuts[l]);}return f[l][r]=ans;}public int minCost(int n, int[] Cuts) {Arrays.sort(Cuts);sz=Cuts.length; cuts = new int[sz+2]; m=cuts.length; INF=0x3f3f3f3f; f = new int[m][m];System.arraycopy(Cuts, 0, cuts, 1, sz); cuts[m-1]=n;for (int i=0; i<m; i++) Arrays.fill(f[i], INF);return dfs(0, m-1);}
}

复杂度分析

• Time： O ( n × m 2 ) O(n × m^2) O(n×m2)，
• Space： O ( m 2 ) O(m^2) O(m2)