题目： 最大平均值和的分组

  • 我们将给定的数组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内被视为是正确的。

来源：力扣（LeetCode）第813题

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

分析：

  • 动态规划题
  • 这次的状态不算难找，主要是在到底应该用三维dp还是二维就可以搞定了。
  • 最后发现二维就够了。
  • 先来说说三维，定义i，j，k分别表示当前为第i份，从数组的下标j开始，到k结束。
  • 于是我将每一种情况全部都可以算一遍，看看哪儿种最大。可是之后我发现，我并不一定要将所有的j到k的情况都存下来，我只要每次将到k为止，或者从j开始归在一起，把最大的那种情况存起来就可以了。
  • 因为下一次找的肯定是上一次分割的尾巴。如果都是以k结束的那么我只要知道最大的就行了，小的根本就用不到。
  • 因此，我们的状态就变成二维的了，即定义i，j为当前为第i份，从0到下标j为止最大的平均数和。

代码：

class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int len = A.length;
        double[][] dp = new double[K][len];
        // i 第几份  j 到j为止
        dp[0][0] = A[0]; // base case
        // 把第一行的情况拿出来，注意不能到达最后K-1个，因为最少也要分1个，如果还要分两个的话，最少也要留两个才行。
        for (int i = 1; i < len - K + 1; i++) dp[0][i] = dp[0][i-1] + A[i];
        // 先取和，再求平均值
        for (int i = 1; i < len - K + 1; i++) dp[0][i] /= (i + 1);
        for (int i = 1; i < K; i++) {
            for (int j = i; j <= len - K + i; j++) {
                // count 用于算出和后求平均值
                int count = j - i + 1;
                // st 即每种情况的开始，我说过把到j结束的归在一起，但还是要计算的，不然怎么得到最大值。
                for (int st = i; st <= j; st++) {
                    double sum = 0;
                    for (int k = st; k <= j; k++) sum += A[k];// 拿到区域和
                    // 算一下当前区域的平均值是否最大。
                    // 由于st是当前区域的开始，所以上一次分割最后一定是st-1，那么就找上一次以st-1为结尾的最大值。
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][st-1] + sum / count);
                    // 一轮循环结束后，除数也会减少，比如原来是1 2 3，现在是2 3的和那么现在只有两个数了。
                    --count;
                }
            }
        }
        // 这里为什么只要len-1而不要其他的情况呢，因为最后一次一定要分到最后，也就是说我不管从谁开始分，一定要以len-1结束。
        return dp[K-1][len-1];
    }
}
  • 写完之后发现，这段代码可以写的更简洁，更优化。
  • 比如我要找区域和，那么我只要先求出所有的前缀和，再将两个前缀和相减就能得到某一个区域的区域和。

  • 同时我对count也做了处理，不需要count变量了。

    class Solution {
public double largestSumOfAverages(int[] A, int K) {
    int len = A.length;
    double[][] dp = new double[K][len];
    // i 第几份  j 到j为止
    double[] sum = new double[len];sum[0] = A[0];
    for (int i = 1; i < len; i++) sum[i] = sum[i-1] + A[i];
    for (int i = 0; i < len - K + 1; i++) dp[0][i] = sum[i] / (i + 1);
    for (int i = 1; i < K; i++) {
        for (int j = i; j <= len - K + i; j++) {
            for (int st = i; st <= j; st++) 
                dp[i][j] = Math.max(dp[i][j], dp[i-1][st-1] + (sum[j] - sum[st-1]) / (j - st + 1));
        }
    }
    return dp[K-1][len-1];
}
}