LeetCode-813. 最大平均值和的分组【动态规划，前缀和】

题目描述：

给定数组 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] <= 10⁴
1 <= k <= nums.length
https://leetcode.cn/problems/largest-sum-of-averages/

解题思路一：动态规划+前缀和。核心思想是，分为K份的结果是分为K-1份结果与后面元素的平均值之和的最大值。例如：

nums = [9,1,2,3,9], k = 3

[9]、[1,2,3,9] = dp[0][2]+avg(1,2,3,9) = a （9分割成2份的答案+9后面的那份 = 整体分割成3份的答案）
[9,1]、[2,3,9] = dp[1][2]+avg(2,3,9)   = b （[9,1]分割成2份的答案+[9,1]后面的那份 = 整体分割成3份的答案）
[9,1,2]、[3,9] = dp[2][2]+avg(3,9)     = c （[9,1,2]分割成2份的答案+[9,1,2]后面的那份 = 整体分割成3份的答案）
[9,1,2,3]、[9] = dp[3][2]+avg(9)       = d （[9,1,2,3]分割成2份的答案+[9,1,2,3]后面的那份 = 整体分割成3份的答案）

所以dp[3][3] = max( a,b,c,d )
这里你可以认为dp[0][2]、dp[1][2]、dp[2][2]、dp[3][2]已经求出了。
1
2
3
4
5
6
7

有不懂的地方看注释就明白了

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        //状态：数组A的每个元素，分割为K个相邻的数组
        //选择：枚举所有分割k的可能性，分割成k份 == 分割成k-1份+最后一份
        int n=nums.size();
        vector<double> sum(nums.size()+1,0.0);//前缀和，要求平均值所以用double
        vector<vector<double>> dp(nums.size()+1,vector<double>(k+1,0));//第一维是前x个数，第二位是x个数分为k份的结果。
        for(int i =1;i<=n;++i) sum[i]=sum[i-1]+nums[i-1];//前缀和，求平均值用
        for(int i =1;i<=n;++i){
            dp[i][1]=sum[i]/i;
            for(int K=2;K<=k&&K<=i;++K)
                for(int j=1;j<i;++j)
                    dp[i][K]=max(dp[i][K],dp[j][K-1]+(sum[i]-sum[j])/(i-j));//分为K份时取，K-1份的最大值与前缀和
        }
        return dp[n][k];//n个数分为k份的答案。
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：O($k\ast n^2$)//三层循环
空间复杂度：O(k*n)//二维数组

解题思路二：一维数组。

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        vector<double> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            dp[i] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = n; i >= j; i--) {
                for (int x = j - 1; x < i; x++) {
                    dp[i] = max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：O($k\ast n^2$)//三层循环
空间复杂度：O(n)//一维数组

解题思路三：0

1