题目
我们将给定的数组 A 分成 K 个相邻的非空子数组 ,我们的分数由每个子数组内的平均值的总和构成。
计算我们所能得到的最大分数是多少。...注意我们必须使用 A 数组中的每一个数进行分组,并且分数不一定需要是整数。...示例:
输入:
A = [9,1,2,3,9]
K = 3
输出: 20
解释:
A 的最优分组是[9], [1, 2, 3], [9]....这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值....解题
dp[i][k] 表示,以 i 结束的时候,切分了k段,所有平均值和的最大值
预先求出前缀和 presum
dp[j][k]=max(dp[j][k],dp[i][k−1]+(presum[j]