LeetCode每日一题系列
题目：813. 最大平均值和的分组
难度：普通
题目
给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。
注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。
示例
示例 1:
输入: nums = [9,1,2,3,9], k = 3
输出: 20.00000
解释: nums 的最优分组是[9], [1, 2,3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. 我们也可以把 nums 分成[9, 1], [2], [3, 9]. 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
示例 2:
输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000
提示:
1 <= nums.length <= 100
1 <= nums[i] <= 104
1 <= k <= nums.length文章来源：https://www.toymoban.com/news/detail-635961.html
思路
动态规划：
首先可以证明的要想分组的平均值只和最大，那么组数一定为k
其次使用动态规划文章来源地址https://www.toymoban.com/news/detail-635961.html
- dp[i][j]表示分到nums[i]这个元素时分了j组的最大平均值之和
- 状态转移方程分为两种情况：
1、当j=1时，dp[i][j]就为nums从0到i-1的平均值
2、当j>1时，将区间分为[0, x-1],[x, i-1]， 其中 x≥j−1，这时方程就变为
题解
class Solution:
def largestSumOfAverages(self, nums: List[int], k: int) -> float:
n = len(nums)
#记录前缀数组便于j=1的情况求均值
prefix = list(accumulate(nums, initial=0))
dp = [[0.0] * (k + 1) for _ in range(n + 1)]
# j=1
for i in range(1, n + 1):
dp[i][1] = prefix[i] / i
# 状态转移
for j in range(2, k + 1):
for i in range(j, n + 1):
for x in range(j - 1, i):
dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x))
return dp[n][k]
到了这里，关于LeetCode每日一题——813. 最大平均值和的分组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
