1547. 切棍子的最小成本-cangjie

题目

1547. 切棍子的最小成本

思路

改写自官方题解官方题解

代码

import std.sort.SortExtension
class Solution {func minCost(n: Int64, cuts: Array<Int64>): Int64 {var size = cuts.sizevar myCuts = ArrayList(cuts)myCuts.sortBy(stable: true){ rht: Int64, lht: Int64 =>if (rht < lht) {return Ordering.LT}if (rht > lht) {return Ordering.GT}return Ordering.EQ}myCuts.insert(0,0)myCuts.append(n)// for(cut in myCuts){//     print("${cut} ")// }// println()var dp = Array<Array<Int64>>(size+2, item:Array<Int64>())for(i in 0..size+2){dp[i] = Array<Int64>(size+2, item:0)}for(i in size..=1 : -1){for(j in i..=size){// println("i = ${i}, j = ${j}")if(i == j){dp[i][j] = 0}else{dp[i][j] = Int64(Int32.Max)}for(k in i..=j){dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])}dp[i][j] += myCuts[j+1] - myCuts[i-1]}}// for(i in 0..size+2){//     for(j in 0..size+2){//         print(dp[i][j])//         print(" ")//     }//     println()// }return dp[1][size]}
}

复杂度

遇到的坑

嵌套数组初始化问题

var dp = Array<Array<Int64>>(size+2, item:Array<Int64>())
for(i in 0..size+2){dp[i] = Array<Int64>(size+2, item:0)
}

结果

cangjie