813. 最大平均值和的分组

813. 最大平均值和的分组

难度中等283

给定数组 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^4
• 1 <= k <= nums.length

思路:熟悉区间DP的同学应该对这题很熟悉，我们约定dp[i][j][k]表示区间[i,j]划分成k部分能够得到的最大平均值和，那么对于一个区间[L,R]，要求它划分成num部分的最大平均值和，首先我们知道num个部分可以看成num-1个部分加上1个部分，因此我们需要枚举分割点M，得到两部分区间[L,M]，[M+1,R]，这两部分有一个划分成num-1部分，有一个仅仅划分成1部分，存在两种情况，dp[L][M][num-1] + dp[M+1][R][1] 和 dp[L][M][1] + dp[M+1][R][num-1]，因此状态转移方程可按照如下表示:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        //区间dp
        int L, R, n = nums.size(), M, num;
        for(int idx = 1; idx < n; ++ idx){
            nums[idx] += nums[idx - 1];
        }
        double dp[101][101][101]{0},  max_value = 0;
 
        for(num = 1; num <= k; ++ num){
            for(L = 0; L < n; ++ L){
                for(R = L; R < n; ++ R){
                    if(num == 1){
                        dp[L][R][1] = (nums[R] - (L == 0 ? 0 : nums[L - 1])) / 1.0 / (R - L + 1);
                    }else if(R - L + 1 >= num){
                        //枚举分割点
                        for(M = L; M < R; ++ M){
                            dp[L][R][num] = max(dp[L][R][num], max(R - M >= num - 1 ? dp[L][M][1] + dp[M + 1][R][num - 1] : 0, M - L + 1 >= num - 1 ? dp[L][M][num - 1] + dp[M + 1][R][1] : 0));
                        }
                    }
                }
            }
 
            max_value = max(max_value, dp[0][n - 1][num]);
        }
        return max_value;
    }
};

优化：

        1.本题如果按照上面所述考虑任意的[L,R]，那么会需要枚举L，造成状态的大量计算，能不能减少点？其实是可以的，我们一步一步分析。首先本题要求的是nums数组最多划分成k个部分，求最大平均值和，那么其实还是区间合并的问题，不过我们想要略去L的枚举，我们使用dp[y][t]表示[0,x]区间划分为t部分的最大平均值和，那么对于一个x>y，存在转移方程

dp[x][t+1]=max{dp[y][t]+Avg(y+1,x)}

即可以理解为，是在原区间[0,y]划分为t部分的基础上，增加一个[y+1,x]的区间得到[0,x]区间上划分为t+1个部分的结果。

        2.能够得到最大平均和的一定是划分为k个部分，证明：不妨设合并前两个部分的区间为[i,h],[h+1,j]，合并后变为[i,j]，合并前这部分对答案的贡献为

合并后这部分对答案的贡献为

为了比较这两部分的大小，我们不妨做个除法

 我们发现，拆分成两部分之后，得到的答案不可能会比原方式要小(仅当所有情况下的子数组的和都为0的情况下)，然而本题中说明了1<=nums[i]<=10^4，因此拆分后答案肯定更大。

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        //区间dp
        int x, y, n = nums.size(), M, num;
        for(int idx = 1; idx < n; ++ idx){
            nums[idx] += nums[idx - 1];
        }
        double dp[101][101]{0},  max_value = 0;
 
        for(num = 1; num <= k; ++ num){
            for(x = 0; x < n; ++ x){
                if(num == 1){
                    dp[x][1] = nums[x] * 1.0 / (x + 1);
                }else{
                    for(y = max(0, num - 2); y < x; ++ y){
                        dp[x][num] = max(dp[x][num], dp[y][num - 1] + (nums[x] - nums[y]) * 1.0 / (x - y));
                    } 
                }
            }
        }
        return dp[n-1][k];
    }
};