Hard

题目描述

给你一个整数数组 nums 和一个整数 k。

将数组分割成若干个非空子数组。分割的代价是分割中每个子数组重要性值的总和。

设 trimmed(subarray) 是子数组的一个版本，其中删除了所有只出现一次的数字。

  • 例如，trimmed([3,1,2,4,3,4]) = [3,4,3,4]。

子数组的重要性值是 k + trimmed(subarray).length。

  • 例如，如果子数组是 [1,2,3,3,3,4,4]，那么 trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4]。这个子数组的重要性值将是 k + 5。

返回 nums 分割的最小可能代价。

子数组是数组中连续的非空元素序列。

示例 1：

输入：nums = [1,2,1,2,1,3,3], k = 2
输出：8
解释：我们将 nums 分割为两个子数组：[1,2], [1,2,1,3,3]。
[1,2] 的重要性值是 2 + (0) = 2。
[1,2,1,3,3] 的重要性值是 2 + (2 + 2) = 6。
分割的代价是 2 + 6 = 8。可以证明这是所有可能分割中的最小代价。

示例 2：

输入：nums = [1,2,1,2,1], k = 2
输出：6
解释：我们将 nums 分割为两个子数组：[1,2], [1,2,1]。
[1,2] 的重要性值是 2 + (0) = 2。
[1,2,1] 的重要性值是 2 + (2) = 4。
分割的代价是 2 + 4 = 6。可以证明这是所有可能分割中的最小代价。

示例 3：

输入：nums = [1,2,1,2,1], k = 5
输出：10
解释：我们将 nums 分割为一个子数组：[1,2,1,2,1]。
[1,2,1,2,1] 的重要性值是 5 + (3 + 2) = 10。
分割的代价是 10。可以证明这是所有可能分割中的最小代价。

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < nums.length
  • 1 <= k <= 10^9

解题思路

这是一个动态规划问题，核心在于理解子数组重要性值的计算和状态转移。

解题思路：

  1. 状态定义：设 dp[i] 表示前 i 个元素的最小分割代价。

  2. 状态转移：对于位置 i，我们需要枚举所有可能的分割点 j，使得子数组 nums[j..i-1] 作为一个完整的分割段。转移方程为：

    dp[i] = min(dp[j] + importance(nums[j..i-1])) for all 0 <= j < i

  3. 重要性值计算优化：关键在于高效计算子数组的重要性值。重要性值 = k + trimmed长度，其中trimmed长度是出现次数 ≥ 2 的元素总数。

  4. 优化策略：对于固定的右端点 i，当左端点 j 从 i-1 递减到 0 时，我们可以增量地维护频率表和trimmed长度：

    • 新增元素首次出现：trimmed长度不变
    • 新增元素第二次出现：trimmed长度 +2（该元素的两个副本都计入）
    • 新增元素第三次及以上出现：trimmed长度 +1

  5. 时间复杂度：通过这种增量计算方式，我们将计算所有子数组重要性值的复杂度从 O(n³) 优化到 O(n²)。

这种方法既保证了正确性，又具有良好的时间效率，是解决此类动态规划+计数问题的典型思路。

代码实现

class Solution {
public:
    int minCost(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            vector<int> freq(n, 0);
            int trimmed = 0;
            
            for (int j = i - 1; j >= 0; j--) {
                freq[nums[j]]++;
                if (freq[nums[j]] == 2) {
                    trimmed += 2;
                } else if (freq[nums[j]] > 2) {
                    trimmed++;
                }
                
                if (dp[j] != INT_MAX) {
                    dp[i] = min(dp[i], dp[j] + k + trimmed);
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def minCost(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(1, n + 1):
            freq = [0] * n
            trimmed = 0
            
            for j in range(i - 1, -1, -1):
                freq[nums[j]] += 1
                if freq[nums[j]] == 2:
                    trimmed += 2
                elif freq[nums[j]] > 2:
                    trimmed += 1
                
                if dp[j] != float('inf'):
                    dp[i] = min(dp[i], dp[j] + k + trimmed)
        
        return dp[n]

public class Solution {
    public int MinCost(int[] nums, int k) {
        int n = nums.Length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = int.MaxValue;
        }
        
        for (int i = 1; i <= n; i++) {
            int[] freq = new int[n];
            int trimmed = 0;
            
            for (int j = i - 1; j >= 0; j--) {
                freq[nums[j]]++;
                if (freq[nums[j]] == 2) {
                    trimmed += 2;
                } else if (freq[nums[j]] > 2) {
                    trimmed++;
                }
                
                if (dp[j] != int.MaxValue) {
                    dp[i] = Math.Min(dp[i], dp[j] + k + trimmed);
                }
            }
        }
        
        return dp[n];
    }
}

var minCost = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 0; i < n; i++) {
        if (dp[i] === Infinity) continue;
        
        const count = new Map();
        let trimmedLength = 0;
        
        for (let j = i; j < n; j++) {
            const num = nums[j];
            const prevCount = count.get(num) || 0;
            count.set(num, prevCount + 1);
            
            if (prevCount === 1) {
                trimmedLength += 2;
            } else if (prevCount > 1) {
                trimmedLength++;
            }
            
            const cost = k + trimmedLength;
            dp[j + 1] = Math.min(dp[j + 1], dp[i] + cost);
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环n次，内层循环平均n/2次，计算重要性值为O(1)
空间复杂度O(n)dp数组和频率数组的空间开销

相关题目