Hard

题目描述

给你一根长度为 n 个单位的木棍，木棍从 0 到 n 标记。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按任意顺序完成切割。每次切割的成本都是当前要切割的棍子的长度，总成本是所有切割成本的总和。当你切一根棍子时，这根棍子会分成两根较小的棍子（它们的长度之和就是切割前棍子的长度）。请参考第一个示例来更好地理解这个问题。

请返回切割的最小总成本。

示例 1：

输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按顺序 [1, 3, 4, 5] 切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二段棍子），第三次切割长度为 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
重新安排切割的顺序为 [3, 5, 1, 4] 例如，将导致总成本 = 16（如示例图所示，7 + 4 + 3 + 2 = 16）。

示例 2：

输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。存在很多总成本 <= 25 的切割顺序，例如，[4, 6, 5, 2, 1] 的总成本 = 22，这是所有可能顺序中成本最小的。

提示：

  • 2 <= n <= 10^6
  • 1 <= cuts.length <= min(n - 1, 100)
  • 1 <= cuts[i] <= n - 1
  • cuts 数组中的所有整数都 互不相同 。

解题思路

这是一个经典的区间动态规划问题。核心思想是通过分治的方式，找到最优的切割顺序。

问题分析：

  • 每次切割的成本等于当前棍子的长度
  • 我们需要找到最优的切割顺序使总成本最小
  • 关键观察：无论以什么顺序切割，最终的棍子分段情况是确定的，只是中间过程不同

解题思路：

  1. 预处理：将切割位置数组排序，并在两端添加0和n，方便处理边界
  2. 状态定义：dp[i][j] 表示在区间 [cuts[i], cuts[j]] 内完成所有切割的最小成本
  3. 状态转移：对于区间 [i, j]，尝试所有可能的中间切割点k，状态转移方程为：
    dp[i][j] = min(dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
    其中 cuts[j] - cuts[i] 是当前棍子的长度
  4. 遍历顺序：按区间长度从小到大遍历，确保子问题已经求解

这个算法的时间复杂度为 O(m³)，其中m是切割点的数量，空间复杂度为 O(m²)。

代码实现

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0);
        cuts.push_back(n);
        sort(cuts.begin(), cuts.end());
        
        int m = cuts.size();
        vector<vector<int>> dp(m, vector<int>(m, 0));
        
        for (int len = 2; len < m; len++) {
            for (int i = 0; i + len < m; i++) {
                int j = i + len;
                dp[i][j] = INT_MAX;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
                }
            }
        }
        
        return dp[0][m - 1];
    }
};

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.extend([0, n])
        cuts.sort()
        
        m = len(cuts)
        dp = [[0] * m for _ in range(m)]
        
        for length in range(2, m):
            for i in range(m - length):
                j = i + length
                dp[i][j] = float('inf')
                for k in range(i + 1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
        
        return dp[0][m - 1]

public class Solution {
    public int MinCost(int n, int[] cuts) {
        var cutsList = cuts.ToList();
        cutsList.Add(0);
        cutsList.Add(n);
        cutsList.Sort();
        
        int m = cutsList.Count;
        int[,] dp = new int[m, m];
        
        for (int len = 2; len < m; len++) {
            for (int i = 0; i + len < m; i++) {
                int j = i + len;
                dp[i, j] = int.MaxValue;
                for (int k = i + 1; k < j; k++) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j] + cutsList[j] - cutsList[i]);
                }
            }
        }
        
        return dp[0, m - 1];
    }
}

var minCost = function(n, cuts) {
    cuts.push(0, n);
    cuts.sort((a, b) => a - b);
    
    const m = cuts.length;
    const dp = Array(m).fill().map(() => Array(m).fill(0));
    
    for (let len = 2; len < m; len++) {
        for (let i = 0; i + len < m; i++) {
            const j = i + len;
            dp[i][j] = Infinity;
            for (let k = i + 1; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
            }
        }
    }
    
    return dp[0][m - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m³)，其中 m 是切割点的数量，三层循环遍历所有区间和分割点
空间复杂度O(m²)，使用二维 DP 数组存储所有区间的最小成本

相关题目