813. 最大平均值和的分组（难度：中等）

题目链接：https://leetcode.cn/problems/largest-sum-of-averages/

题目描述：

给定数组 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] <= 10^4
• 1 <= k <= nums.length

解法：动态规划+前缀和

题目意思：将数组nums 分成最多K个相邻的子数组，计算平均值之和。数组拆分的越多，平均值之和一定是越大的。所以一定是分到K组，平均值之和最大。

定义数组f[i][j]为将前i个元素分成j组的最大平均值之和。

• 当 j = 1时，此时有 f[i][j] = (nums[0] + nums[1] + ... + nums[i-1]) / i
• 当 j > 1时，f[k-1][j-1] + (nums[k] + nums[k+1] + ... + nums[i-1]) / (i - k + 1)。

计算连续段之和，可以使用前缀和进行优化。

代码：

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int len = nums.length;
        double[] sum = new double[len + 1];
        for (int i = 1; i <= len; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        double[][] dp = new double[len + 1][k + 1];
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                if (j == 1) {
                    dp[i][1] = sum[i] / i;
                } else {
                    for (int m = 2; m <= i; m++) {
                        dp[i][j] = Math.max(dp[i][j], dp[m - 1][j - 1] + (sum[i] - sum[m - 1]) / (i - m + 1));
                    }
                }
            }
        }
        return dp[len][k];
    }
}