区间 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)
更多推荐
【区间 dp】A028
发布评论