将数组分成最小总代价的子数组 I

难度: 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 。
其他得到 3 个子数组的方案是：
- [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

Submission

运行时间: 21 ms

内存: 16.1 MB

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        newArr = [nums[0]] + sorted(nums[1:])
        print(newArr[:3])
        return sum(newArr[:3])

Explain

这个题解的思路是首先保留数组的第一个元素，然后将数组的剩余部分进行排序。排序后，为了最小化总代价，选择排序后的前三个元素（包括第一个原始元素）作为三个子数组的首元素。这样做是基于假设，排序后的前三个元素将会是最小的三个数，从而保证分割成三个子数组后的总代价最低。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        # 创建一个新数组，其中第一个元素是原数组的第一个元素
        newArr = [nums[0]] + sorted(nums[1:])
        # 打印新数组的前三个元素，用于调试
        print(newArr[:3])
        # 返回新数组前三个元素的和，这是三个子数组的最小总代价
        return sum(newArr[:3])

Explore

是的，题解中的方法确实会影响原数组的连续性。排序操作改变了元素的原始顺序，导致无法从排序后的数组中直接得到原数组的连续子数组。因此，这种方法不能保证分割出的子数组满足题目要求的连续性。

这种方法不能确保能在原数组中找到三个连续的子数组，使得每个子数组的首元素是排序后的前三个元素。排序操作改变了元素间的相对位置，所以即使这三个元素是最小的，也不意味着在原数组中它们是连续的或能形成连续的子数组。

题解没有考虑这一点。虽然选择最小的三个元素作为各子数组的首元素可以初步降低代价，但由于子数组是连续的，后续元素可能会很大，从而实际增加了子数组的代价。因此，简单地选取最小的三个元素而不考虑它们在原数组中的位置和连续性，可能不会得到最优的总代价。