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])}')运行实例一
pls input nums=[1,2,3]
pls input k=1
最优方案是[[1, 2, 3]],该分割方案的分数为21
运行实例二
pls input nums=[1,2,3,4,5]
pls input k=2
最优方案是[[1, 2, 3], [4, 5]],该分割方案的分数为66
运行实例三
pls input nums=[5,4,2,1]
pls input k=3
最优方案是[[5], [4], [2, 1]],该分割方案的分数为31
运行实例四
pls input nums=[1,3,5,7,9]
pls input k=4
最优方案是[[1, 3], [5], [7], [9]],该分割方案的分数为98
