813. 最大平均值和的分组

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/largest-sum-of-averages/
Star
我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。
注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。
示例:输入:
A = [9,1,2,3,9]
K = 3
输出: 20
解释:
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
说明:
  • 1 <= A.length <= 100.
  • 1 <= A[i] <= 10000.
  • 1 <= K <= A.length.
  • 答案误差在 10^-6 内被视为是正确的。

法1 动态规划 第一类区间型

思路
同
📃
1278. 分割回文串 III
 
题解
class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        K = k
        dp = [[0] * (K+1) for _ in nums]

        sum_ = 0
        for i in range(0, len(nums)):
            sum_ += nums[i]
            dp[i][1] = sum_ / (i+1)

        for i in range(0, len(nums)):
            for k in range(2, K+1):
                # nums[i]只有 i + 1 个数字 不够分 k 份
                if k > i + 1:
                    break
                # 找第 k 份的起始位置，是包含j的
                for j in range(i, -1, -1):
                    # j-1 前面的数字不够 k - 1 份了
                    if j < k - 1:
                        break
                    temp = nums[j:i+1]
                    dp[i][k] = max(dp[i][k], dp[j-1][k-1] + sum(temp) / len(temp))              

        return dp[-1][K]