Hard

题目描述

给定两个大小相同的整数数组 nums 和 cost，以及一个整数 k。

你可以将 nums 分成若干个子数组。第 i 个子数组由元素 nums[l..r] 组成，其代价为：

(nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r])

注意 i 表示子数组的顺序：第一个子数组为 1，第二个为 2，以此类推。

返回任何有效分割的最小总代价。

示例 1：

输入：nums = [3,1,4], cost = [4,6,6], k = 1
输出：110
解释：
最小总代价可以通过将 nums 分成子数组 [3, 1] 和 [4] 来实现。
- 第一个子数组 [3,1] 的代价是 (3 + 1 + 1 * 1) * (4 + 6) = 50。
- 第二个子数组 [4] 的代价是 (3 + 1 + 4 + 1 * 2) * 6 = 60。

示例 2：

输入：nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7
输出：985
解释：
最小总代价可以通过将 nums 分成子数组 [4, 8, 5, 1]、[14, 2, 2] 和 [12, 1] 来实现。
- 第一个子数组 [4, 8, 5, 1] 的代价是 (4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525。
- 第二个子数组 [14, 2, 2] 的代价是 (4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250。
- 第三个子数组 [12, 1] 的代价是 (4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210。

约束：

  • 1 <= nums.length <= 1000
  • cost.length == nums.length
  • 1 <= nums[i], cost[i] <= 1000
  • 1 <= k <= 1000

解题思路

这道题需要使用动态规划来求解。关键在于理解代价计算公式的含义和状态转移。

首先分析代价公式：第 i 个子数组 nums[l..r] 的代价是 (nums[0] + ... + nums[r] + k * i) * (cost[l] + ... + cost[r])。这里有两个重要观察：

  1. 代价中包含 nums[0] 到 nums[r] 的前缀和，意味着后面的子数组会受到前面所有元素的影响
  2. 每个子数组还要加上 k * i，其中 i 是子数组的序号

定义状态 dp[i] 表示从位置 i 开始到数组末尾的最小分割代价。对于每个位置 i，我们可以选择在任意位置 j (j >= i) 结束第一个子数组，然后递归处理剩余部分。

状态转移时需要注意：当我们确定第一个子数组为 nums[i..j] 时，这个子数组的序号取决于前面已经有多少个子数组。由于我们从后往前计算，需要巧妙地处理这个依赖关系。

通过预计算前缀和来优化区间和的计算，整体算法复杂度为 O(n³)。

代码实现

class Solution {
public:
    long long minimumCost(vector<int>& nums, vector<int>& cost, int k) {
        int n = nums.size();
        vector<long long> prefixNums(n + 1, 0), prefixCost(n + 1, 0);
        
        for (int i = 0; i < n; i++) {
            prefixNums[i + 1] = prefixNums[i] + nums[i];
            prefixCost[i + 1] = prefixCost[i] + cost[i];
        }
        
        vector<vector<long long>> memo(n + 1, vector<long long>(n + 1, -1));
        
        function<long long(int, int)> dp = [&](int pos, int subarrays) -> long long {
            if (pos == n) return 0;
            if (memo[pos][subarrays] != -1) return memo[pos][subarrays];
            
            long long result = LLONG_MAX;
            for (int end = pos; end < n; end++) {
                long long numsSum = prefixNums[end + 1];
                long long costSum = prefixCost[end + 1] - prefixCost[pos];
                long long currentCost = (numsSum + (long long)k * subarrays) * costSum;
                long long remainingCost = dp(end + 1, subarrays + 1);
                result = min(result, currentCost + remainingCost);
            }
            
            return memo[pos][subarrays] = result;
        };
        
        return dp(0, 1);
    }
};

class Solution:
    def minimumCost(self, nums: List[int], cost: List[int], k: int) -> int:
        n = len(nums)
        prefix_nums = [0] * (n + 1)
        prefix_cost = [0] * (n + 1)
        
        for i in range(n):
            prefix_nums[i + 1] = prefix_nums[i] + nums[i]
            prefix_cost[i + 1] = prefix_cost[i] + cost[i]
        
        memo = {}
        
        def dp(pos, subarrays):
            if pos == n:
                return 0
            if (pos, subarrays) in memo:
                return memo[(pos, subarrays)]
            
            result = float('inf')
            for end in range(pos, n):
                nums_sum = prefix_nums[end + 1]
                cost_sum = prefix_cost[end + 1] - prefix_cost[pos]
                current_cost = (nums_sum + k * subarrays) * cost_sum
                remaining_cost = dp(end + 1, subarrays + 1)
                result = min(result, current_cost + remaining_cost)
            
            memo[(pos, subarrays)] = result
            return result
        
        return dp(0, 1)

public class Solution {
    public long MinimumCost(int[] nums, int[] cost, int k) {
        int n = nums.Length;
        long[] prefixNums = new long[n + 1];
        long[] prefixCost = new long[n + 1];
        
        for (int i = 0; i < n; i++) {
            prefixNums[i + 1] = prefixNums[i] + nums[i];
            prefixCost[i + 1] = prefixCost[i] + cost[i];
        }
        
        Dictionary<(int, int), long> memo = new Dictionary<(int, int), long>();
        
        long Dp(int pos, int subarrays) {
            if (pos == n) return 0;
            if (memo.ContainsKey((pos, subarrays))) return memo[(pos, subarrays)];
            
            long result = long.MaxValue;
            for (int end = pos; end < n; end++) {
                long numsSum = prefixNums[end + 1];
                long costSum = prefixCost[end + 1] - prefixCost[pos];
                long currentCost = (numsSum + (long)k * subarrays) * costSum;
                long remainingCost = Dp(end + 1, subarrays + 1);
                result = Math.Min(result, currentCost + remainingCost);
            }
            
            memo[(pos, subarrays)] = result;
            return result;
        }
        
        return Dp(0, 1);
    }
}

var minimumCost = function(nums, cost, k) {
    const n = nums.length;
    const dp = new Array(n).fill(Infinity);
    
    // Precompute prefix sums
    const prefixNums = new Array(n + 1).fill(0);
    const prefixCost = new Array(n + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        prefixNums[i + 1] = prefixNums[i] + nums[i];
        prefixCost[i + 1] = prefixCost[i] + cost[i];
    }
    
    // dp[i] = minimum cost to divide nums[0...i]
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= i; j++) {
            // Consider subarray from j to i
            const subarrayIndex = dp[j] === Infinity ? 1 : 
                (j === 0 ? 1 : getSubarrayCount(j - 1, dp) + 1);
            
            const subarraySum = prefixNums[i + 1] - prefixNums[j];
            const subarrayCostSum = prefixCost[i + 1] - prefixCost[j];
            const totalSum = prefixNums[i + 1] + k * subarrayIndex;
            const currentCost = totalSum * subarrayCostSum;
            
            if (j === 0) {
                dp[i] = Math.min(dp[i], currentCost);
            } else {
                dp[i] = Math.min(dp[i], dp[j - 1] + currentCost);
            }
        }
    }
    
    return dp[n - 1];
    
    function getSubarrayCount(index, dp) {
        let count = 0;
        for (let i = 0; i <= index; i++) {
            for (let j = 0; j <= i; j++) {
                if ((j === 0 && dp[i] === getCost(0, i, 1)) || 
                    (j > 0 && dp[i] === dp[j - 1] + getCost(j, i, getSubarrayCount(j - 1, dp) + 1))) {
                    return getSubarrayCount(j - 1, dp) + 1;
                }
            }
        }
        return count;
    }
    
    function getCost(start, end, subarrayIndex) {
        const subarraySum = prefixNums[end + 1] - prefixNums[start];
        const subarrayCostSum = prefixCost[end + 1] - prefixCost[start];
        const totalSum = prefixNums[end + 1] + k * subarrayIndex;
        return totalSum * subarrayCostSum;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n³)
空间复杂度O(n²)

时间复杂度：状态数量为 O(n²)，每个状态需要 O(n) 的时间计算转移，总复杂度为 O(n³)。 空间复杂度：记忆化数组需要 O(n²) 的空间。

相关题目