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

思 路 分 析 ： \color{blue}思路分析： 思路分析：对于这道题，刚开始我想着利用贪心策略来处理，蛋试发现问题远没有贪心策略那么简单。蛋试一般这种数组分割求最大值都是用贪心策略、动态规划，所以转移到动态规划。

在进行动态规划求解之前，我们需要知道如何快速求和数组某一段的和。请先翻阅 LeetCode 区域和检索
本题同样采用这种策略快速计算数组段的和。使用sum[i]记录数组A的前i个元素的和，所以数组段[j, i）的和 = sum[i] - sum[j]

接着就是动态数组以及状态转移方程的构建。

dp[i][k]用于记录A数组前i个元素分成k段平均值和的最大值。
如果k == 1，dp[i][k] = sum[i] * 1.0 / i。代表着把前i个元素分成1段，平均值和的最大值就是自身的平均值
否则dp[i][k] = max(dp[i][k], dp[j][k - 1] + 1.0 * (sum[i] - sum[j]) / (i - j));//其中j∈[1, i)，
	//整个表达式代表把前个元素分成k段最大值 = max(把前j个分成k - 1段，最后[j, i)单独看做一段计算的和)

class Solution { 
public:
    double largestSumOfAverages(vector<int>& A, int K) { 
        int Asize = (int)A.size();
        vector<int> sum(Asize + 1, 0);//sum[i]记录A数组前i个元素的和
        //第一步：使用递推求和的元素计算sum[i]
        for (int i = 1; i <= Asize; ++i){ 
            sum[i] = sum[i - 1] + A[i - 1];
        }
        //dp[i][k]表示把A数组中前i个元素分成K段，最大值
        vector<vector<double>> dp(Asize + 1, vector<double>(K + 1, 0));
        //第二步：开始动态规划
        for (int i = 1; i <= Asize; ++i){ 
            dp[i][1] = 1.0 * sum[i] / i;//把前i个元素分成一段
            for (int k = 2; k <= K && k <= i; ++k){ //计算前i个元素分成[2, K]段（注意k不能超过i，因为i个元素最多分成i段
                for (int j = max(1, k - 1); j < i; ++j){ //把前j个分成K - 1段，将[j, i)分成一段
                	//[1,j]区间段至少1个，并且它需要被分为k-1段，所以j需要从max(1, k - 1)开始穷举（感谢评论区@cumt~提醒）
                    //sum[i] - sum[j]计算的是[j, i）和，方程表示把前j个分成k - 1段，最后[j, i)单独看做一段计算的和
                    dp[i][k] = max(dp[i][k], dp[j][k - 1] + 1.0 * (sum[i] - sum[j]) / (i - j));
                }
            }
        }
        return dp[Asize][K];//把数组前Asize个元素分成K段平均值和的最大值
    }
};