欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-24 17:51:36
...

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份 如下图:

LeetCode 813 最大平均值和的分组 (区间dp)
然后再 1到i+1中,我们可以设置一个j,表示前j个数分成k-1分,j-i+1个数分成1分。 如下图:

LeetCode 813 最大平均值和的分组 (区间dp)
我们可以令 dp[i][k] 表示前i个数,分成k分的最大平均值。

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

所以推出dp:
LeetCode 813 最大平均值和的分组 (区间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];

    }
};
相关标签: ACM 算法集