LeetCode 813 最大平均值和的分组 (区间dp)

LeetCode 813 题目链接：最大平均值和的分组

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

题意分析：
    给出一个长度为n的序列，把这个数列分成k份，每一份的平均值加起来为sum ，求这个最大的sum值。

这道题的突破口是分成K份，我们可以利用这个点去拆分数列。

一个数列从1-n。我们将前i+1的数分成K份 如下图：

然后再 1到i+1中，我们可以设置一个j，表示前j个数分成k-1分，j-i+1个数分成1分。 如下图：

我们可以令 dp[i][k] 表示前i个数，分成k分的最大平均值。

例如dp[5][2] 表示前5个数分成2份，前5个数分成2份的话，有很多种分法，比如，等价于前4个数分成一份和第五个数分成一份，或者前三个数分成一份，后2个数分成1份等等等，一直到前一个数分成一份，后四个数分成一份为止。我们能发现，j的作用就是在不停的枚举前i个数的左区间为前j个数。

所以推出dp：

sum数组是求前缀和。方便计算[l,r]的和，除以区间长度就是区间平均值了。
代码先可以预处理dp[i][1] 。也就是前i个数分成一份的平均值。

区间dp需要三层循环，复杂度是O（n^3）

代码：

class Solution {
public:
    double sum[105];
    double dp[105][105];
    double largestSumOfAverages(vector<int>& A, int K) {

        int n=A.size();
        for(int i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+A[i-1]*1.0;
        }

        for(int i=1;i<=n;i++)
        {
            dp[i][1]=sum[i]*1.0/i*1.0;
        }

        for(int i=1;i<=n;i++)
        {
            for(int k=2;k<=K;k++)
            {
                if(k>i)continue;//前i个数分成k段,如果k>i,不需要计算 
                double maxx=0.0;
                for(int j=1;j<=i;j++)
                {
                    maxx=max(maxx,dp[j][k-1]+(sum[i]-sum[j])*1.0/(i-j)*1.0);
                }
                dp[i][k]=maxx;
            }
        }

        return dp[n][K];

    }
};