给你一个整数数组 nums 和一个整数 k。
你的任务是将 nums 分割成 恰好 k 个子数组,并返回所有有效分割方案中 最小可能的分数。
一个分割方案的 分数 是其所有子数组 值 的 总和。
子数组的 值 定义为 sumArr * (sumArr + 1) / 2,其中 sumArr 是该子数组元素的总和。
子数组 是数组中连续的非空元素序列。
示例 1:
输入: nums = [5,1,2,1], k = 2
输出: 25
解释:
k = 2 个子数组。一种最优方案是 [5] 和 [1, 2, 1]。sumArr = 5,value = 5 × 6 / 2 = 15。sumArr = 1 + 2 + 1 = 4,value = 4 × 5 / 2 = 10。15 + 10 = 25,这是可能的最小分数。示例 2:
输入: nums = [1,2,3,4], k = 1
输出: 55
解释:
k = 1 个子数组,所有元素都属于同一个子数组:[1, 2, 3, 4]。sumArr = 1 + 2 + 3 + 4 = 10,value = 10 × 11 / 2 = 55。示例 3:
输入: nums = [1,1,1], k = 3
输出: 3
解释:
k = 3 个子数组。唯一的有效分割方案是 [1], [1], [1]。sumArr = 1,value = 1 × 2 / 2 = 1。1 + 1 + 1 = 3,这是可能的最小分数。
提示:
1 <= nums.length <= 10001 <= nums[i] <= 1041 <= k <= nums.length