1547. 切棍子的最小成本

棍子的最小成本"/>

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];}
}