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

题目

1547. 切棍子的最小成本

思路

改写自官方题解官方题解

代码

import std.sort.SortExtension
class Solution {
    func minCost(n: Int64, cuts: Array<Int64>): Int64 {
        var size = cuts.size
        var 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