Easy

题目描述

给定一个长度为 n 的整数数组 nums。

数组的代价是其第一个元素的值。例如，[1,2,3] 的代价是 1，而 [3,4,1] 的代价是 3。

你需要将 nums 分割成 3 个不相交的连续子数组。

返回这些子数组代价的最小可能和。

示例 1：

输入：nums = [1,2,3,12]
输出：6
解释：形成 3 个子数组的最佳方式是：[1], [2], 和 [3,12]，总代价为 1 + 2 + 3 = 6。
其他可能的分割方式：
- [1], [2,3], 和 [12]，总代价为 1 + 2 + 12 = 15。
- [1,2], [3], 和 [12]，总代价为 1 + 3 + 12 = 16。

示例 2：

输入：nums = [5,4,3]
输出：12
解释：形成 3 个子数组的最佳方式是：[5], [4], 和 [3]，总代价为 5 + 4 + 3 = 12。
可以证明 12 是可达到的最小代价。

示例 3：

输入：nums = [10,3,1,1]
输出：12
解释：形成 3 个子数组的最佳方式是：[10,3], [1], 和 [1]，总代价为 10 + 1 + 1 = 12。
可以证明 12 是可达到的最小代价。

提示：

  • 3 <= n <= 50
  • 1 <= nums[i] <= 50

解题思路

这道题要求我们将数组分割成 3 个连续的子数组，使得各子数组首元素之和最小。

核心观察：

  • 第一个子数组的代价固定为 nums[0]
  • 我们只需要确定两个分割点位置，来最小化第二和第三个子数组的首元素之和

解法分析：

方法一：暴力枚举（推荐） 由于数组长度较小（最多50），我们可以枚举所有可能的分割点组合：

  • 第一个分割点 i 的范围：[1, n-2]（确保至少有两个子数组）
  • 第二个分割点 j 的范围：[i+1, n-1]（确保第三个子数组非空）

对于每种分割方式 [0...i-1], [i...j-1], [j...n-1]，计算代价 nums[0] + nums[i] + nums[j]，取最小值。

优化思路： 由于 nums[0] 是固定的，我们实际上只需要找到 nums[i] + nums[j] 的最小值，其中 1 <= i < j <= n-1。

时间复杂度 O(n²)，空间复杂度 O(1)，对于本题的数据规模完全足够。

代码实现

class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int n = nums.size();
        int minCost = INT_MAX;
        
        // 枚举所有可能的分割点组合
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = nums[0] + nums[i] + nums[j];
                minCost = min(minCost, cost);
            }
        }
        
        return minCost;
    }
};

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        n = len(nums)
        min_cost = float('inf')
        
        # 枚举所有可能的分割点组合
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                cost = nums[0] + nums[i] + nums[j]
                min_cost = min(min_cost, cost)
        
        return min_cost

public class Solution {
    public int MinimumCost(int[] nums) {
        int n = nums.Length;
        int minCost = int.MaxValue;
        
        // 枚举所有可能的分割点组合
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = nums[0] + nums[i] + nums[j];
                minCost = Math.Min(minCost, cost);
            }
        }
        
        return minCost;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumCost = function(nums) {
    const n = nums.length;
    let minCost = Number.MAX_SAFE_INTEGER;
    
    // 枚举所有可能的分割点组合
    for (let i = 1; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            const cost = nums[0] + nums[i] + nums[j];
            minCost = Math.min(minCost, cost);
        }
    }
    
    return minCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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