Problem: 1547. 切棍子的最小成本

思路

算上起始点（0）和末尾点（n），我们一共可以将整个棍子分为n+1个节点，我们可以建立一个Listnodes，按顺序记录整根棍子中的所有切割点，并包含起始点和末尾点

以该图为例，我们知道cuts=[3,5,1,4]，则nodes=[0,1,3,4,5,7]，实际上，整道题中我们只需要考虑nodes里的节点即可，不在nodes中的节点我们并不需要考虑

不论我们如何决定切割的顺序，第一步必然是从nodes中的某个节点（0和n除外）下刀，并将整根棍子切分为两根子棍，此时总的切割成本即整根棍子的长度n + 两根子棍各自的切割成本，以第一刀从3下刀为例，那么总的切割成本就是

棍子[0-7]的长度7 +棍子[0-3]的切割成本+棍子[3-7]的切割成本

以此类推，思路就很明显了：对于任意一根子棍，遍历子棍中间的切割点，将其切割为目标状态需要的成本，即子棍的长度+切割后得到的两根子棍各自的切割成本，由于题目要求求成本的最小值，我们对于遍历到的所有情况取最小成本即可

设dp[begin][end]为端点坐标为(begin,end)的子棍切割到目标状态需要的最小成本

由于我们需要先求出更短的子棍的成本，才能进一步地求总体的成本（这里的总体仍然可能是整根棍子的某一个子棍），我们应当从截数（或者说子棍中包含的切割点数量/窗口长度/棍子的长度）的从小到大进行遍历

第一次遍历，求[0-1],[1-3],[3-4],[4-5],[5-7]的成本，由于棍子中间没有其他切割点，没必要继续切割，成本为0
第二次遍历，求[0-3],[1-4],[3-5],[4-7]的成本，由于棍子中间只有一个切割点，成本固定为子棍的长度
第三次遍历，求[0-4],[1-5],[3-7]的成本，由于棍子中间有两个切割点，需要遍历切割的可能性取最小值
要注意的是，这里的点坐标并不一定对应dp中的索引，因为我这里dp是只存储了端点和切割点的坐标，以nodes=[0,1,3,4,5,7]为例，则棍子[1-5]的切割成本应当对应dp[1][4]

最终输出dp[0][nodes.size-1]即整个棍子两个端点之间的切割成本即可

复杂度

时间复杂度:
空间复杂度:

Code

class Solution {
    fun minCost(n: Int, cuts: IntArray): Int {
        cuts.sort()
        val nodes = ArrayList<Int>()
        nodes.add(0)
        nodes.addAll(cuts.toList())
        nodes.add(n)

        val dp = Array(nodes.size) { IntArray(nodes.size) { Int.MAX_VALUE } }
        for (len in 1 until nodes.size) {
            for (begin in 0 until nodes.size - 1) {
                val end = begin + len
                if (end >= nodes.size) break
                if (len == 1) {
                    dp[begin][end] = 0
                } else {
                    for (mid in begin + 1..end - 1) {
                        dp[begin][end] =
                            Math.min(dp[begin][end], dp[begin][mid] + dp[mid][end] + (nodes[end] - nodes[begin]))
                    }
                }
            }
        }
        return dp[0][nodes.size - 1]
    }
}

1547. 切棍子的最小成本 - Kotlin 二维DP

思路

复杂度

Code