LC-813 最大平均值和的分组（动态规划(背包问题变形)）

813. 最大平均值和的分组

难度中等250

给定数组

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

动态规划

题解来自：davidditao

令

dp[i][k]

表示：将 nums 中的前 i 个数分成 k 个子数组的最大平均值和。那么：

• k = 1 时，dp[i][1] = (nums[0] + ... + nums[i - 1]) / i;
• k > 1 时，dp[i][k] = max(dp[j][k - 1] + avg[j][i])。j 在 [0, i - 1] 之间。其中 avg[j][i] 为区间 [j, i - 1] 的平均值。avg[j][i] = (nums[j] + ... + nums[i - 1]) / (i - j)。

为了快速计算

avg[j][i]

， 我们可以预处理 nums 的前缀和。

classSolution{publicdoublelargestSumOfAverages(int[] nums,int _K){int n = nums.length;// 前缀和优化int[] sum =newint[n+1];for(int i =1; i <= n; i++){
            sum[i]= sum[i-1]+ nums[i-1];}// dp[i][k] 表示将nums中的前 i 个数分成 k 个子数组的最大平均值和double[][] dp =newdouble[n+1][_K+1];// base case: k = 1，如果分一组for(int i =1; i <= n; i++){
            dp[i][1]=1.0* sum[i]/ i;}for(int i =1; i <= n; i++){// 前 i 个数for(int k =2; k <= _K; k++){// 分成k组for(int j =1; j < i; j++){// [0-j]分为k-1组，[j-i]分为1组，与[0-i]分为k组哪个大double avg =1.0*(sum[i]-sum[j])/(i-j);
                    dp[i][k]=Math.max(dp[i][k], dp[j][k-1]+ avg);}}}return dp[n][_K];}}

tips:

面对这种题目如何想到DP？ ==> 子问题+递归关系（去掉最后元素，问题规模缩小了，变成什么样了？）

像这个题, 要求n个数分成k段, 假设如果最后一个元素独立一段, 那么前面n-1个元素就要分成k-1段; 假设如果最后2个元素独立一段, 那么前面 n-2个元素就要分成k-1段; … 假设如果最后m个元素独立一段, 那么前面 n-m个元素就要分成k-1段; 这个时候就可以看出 f[n][k] 跟 f[n-m][k-1] 有递推关系, f[n][k] = max(f[n-m][k-1] + avg(最后m个元素))

灵神总结：

如何思考动态规划？

1、问题中有哪些变量？

2、重新复述一遍问题，替换变量名

3、（最关键）最后一步发生了什么

4、去掉最后一步，问题规模缩小了，变成什么样了？(子问题)

5、得到状态转移方程

6、初始值和答案分别是多少

(7、)优化转移