棍子的最小成本"/>
1547. 切棍子的最小成本
这题太艰难了!!!
官方题解说的挺好的,贴一下:
对于设定初始值,我可以这样认为,需要计算的值可以把初值先初始化为无穷大,因为再后续状态转移中会消除这种影响,使得初值不会影响到最终结果。对于无法切割或者不成木棍的情况,可以设置为0,不在计算过程中起作用。
class Solution {public int minCost(int n, int[] cuts) {int len = cuts.length;Arrays.sort(cuts);int[] arr = new int[len + 2];System.arraycopy(cuts,0,arr,1,len);arr[0] = 0;arr[len+1] = n;int[][] dp = new int[len+2][len+2];for (int i = len; i >= 1; i--) {for (int j = i ; j <= len; j++) {//初始值 是不成立的dp[i][j] = Integer.MAX_VALUE / 2;for (int k = i; k <= j; k++) {dp[i][j] = Math.min(dp[i][j],dp[i][k-1] + dp[k+1][j] );}dp[i][j] += arr[j+1] - arr[i-1];}}return dp[1][len];}
}
更多推荐
1547. 切棍子的最小成本
发布评论