当前位置：首页 > news >正文

解决leetcode第3826题.最小分割分数问题

news 2026/3/27 2:15:25

3826.最小分割分数

难度：困难

问题描述：

给你一个整数数组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。

该分割方案的分数为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<=1000

1<=nums[i]<=104

1<=k<=nums.length

问题分析：

将nums数组分割成恰好k个子数组，则这k个子数组的长度和必然等nums的长度，把数组nums的长度设为n，这个问题就可以抽象为如何把n分成k个数之和，把各种分法找出之后，再将每一种分法解析为相应的子数组，并求出对应的分数，最后在其中找到最小分数即可。

程序如下：

#把n分成k个数之和，返回各种分法 def get_division_method(n,k): if k==1: return [[n]] elif k==2: t=[] for i in range(1,n): t.append([i,n-i]) return t else: t=[] for i in range(1,n): m=get_division_method(n-i,k-1) for j in m: j.append(i) t.append(j) return t #根据一个分解方案解析生成对应的子数组并返回 def analysis_plan(nums,a): t=[] k=0 for i in a: b=nums[k:k+i] t.append(b) k=k+i return t #计算一个子数组的分数，并返回 def get_score(sub_array): s=sum(sub_array) return s*(s+1)/2 #主程序 nums=eval(input('pls input nums=')) k=int(input('pls input k=')) n=len(nums) a=get_division_method(n,k) score=[] for i in a: t=analysis_plan(nums,i) s=0 for j in t: s+=get_score(j) score.append([t,s]) score.sort(key=lambda x:x[1]) print(f'最优方案是{score[0][0]},该分割方案的分数为{int(score[0][1])}')