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, 但不是最大值.
1
2
3
4
5
6

示例 2:

输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000
1
2

提示:

• 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 的前缀和。

class Solution {
    public double largestSumOfAverages(int[] nums, int _K) {
        int n = nums.length;
        // 前缀和优化
        int[] sum = new int[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 = new double[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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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、)优化转移