题目分析

这个题目和前几天刚刚讲过的周赛第四题完美分割的方案数非常相似，也是使用动态规划进行求解。小伙伴们如果不会求解，可以参考一个题目，然后再独立完成另一个题目。

动态规划

动态规划的重点是找到状态转移方程，状态转移方程的重点是如何将原问题用规模更小的子问题表示。

本题的原问题是前n个数，分成k组的平均值之和，那么如果将最后一个元素单独作为一组的子问题是前n - 1个数，分成k - 1组的平均值之和，如果将最后两个元素单独作为一组的子问题是前n - 2个数，分成k - 1组的平均值之和。以此类推，可以得到状态转移方程。

$$ dp[k][n] = max(dp[k -1][m] + average(nums[m + 1:n])), m >= k - 1$$

这里用到三层循环，遍历dp需要两层，每一层里需要将m遍历n。

算法的时间复杂度为O(kn^2)，空间复杂度为O(n)。这里可以使用滚动数组优化第一维空间复杂度。

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] dp = new double[n + 1];
        double sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            dp[i + 1] = sum / (i + 1);
        }
        for (int i = 2; i <= k; i++) {
            for (int j = n - (k - i); j >= i; j--) {
                sum = 0;
                for (int kk = j - 1; kk >= i - 1; kk--) {
                    sum += nums[kk];
                    dp[j] = Math.max(dp[j], dp[kk] + sum / (j - kk));
                }
            }
        }
        return dp[n];
    }
}

刷题总结

本题是经典的DP问题，需要小伙伴们牢牢掌握。