力扣每日一题：813. 最大平均值和的分组【0-1背包问题】

给定数组

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

分析：题目意思：给出数组nums和可以分出组数k，然后我们可以把数组分成k份而且是连续的，然后再求出每份的分均值，然后在求和，我们要求的是这个和的最大值。其实这个题目就是正中的0-1 背包问题，给定有k个容量，然后价值就是分成子数组的分均值。这里我们可以先求出前缀和来进行优化。有了前缀和，创建一个dp二维数组来记录，然后我们进行当k=1 的时候，初始化dp数组，然后就是套dp背包的板子了

AC代码：

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
       int n = nums.length ; 
        double res[][] = new double[n+1][k+1];
        double suffixSum [] = new double[n+1] ;
        
        for(int i =1 ; i<=n;i++){
            suffixSum[i] = suffixSum[i-1] + nums[i-1] ;
        }
        
        for (int i =1 ; i<=n;i++){
            res [i][1] = suffixSum[i]/i; 
        }
        
        
        for (int i =1 ;i<=n ;i++){
            for (int j = 2;j<=k;j++){
                for (int m=1;m<i;m++){
                    double avg = (suffixSum[i]-suffixSum[m])/(i-m) ;
                    
                    res[i][j] = Math.max(res[i][j],res[m][j-1]+avg) ; 
                }
            }
        }
        
        
        return res[n][k] ; 
    }
}