813. Largest Sum of Averages

Link

Solution

我们定义dp[i][k]表示将A[0]到A[i]这i+1个元素划分成为k组的话，平均数之和的最大值，然后推导递推公式：

1）如果k == 1，说明我们将这i+1个元素归为1组，所以dp[i][k] = avg(A[0],...A[i])；

2）如果k > 1，那么我么可以采用的策略是：将A[j], A[i]这i-j+1个数划分为1组，那么此时就需要将A[0],...A[j - 1]划分成为另外的k-1组（k - 1 <= j <= i）。在这所有的划分方法中，我们需要取使得dp[i][k]达到最大值的那种划分，所以dp[i][k] = max(dp[j - 1][k - 1] + avg(A[j],...A[i])), k - 1 <= j <= i。最后得到的dp[n - 1][K]即为所求。

  public double largestSumOfAverages(int[] A, int K) {

        double[][] dp = new double[A.length+1][K+1];
        double sum = 0;
        for(int i = 0; i < A.length; i++){
            sum += A[i];
            dp[i+1][1] = sum/(i+1);   
        }
        return search(A.length, K, dp, A);
    }
    
    public double search(int end, int group, double[][] memo, int[] A)
    {
        if(end < group) return 0;
        if(memo[end][group] != 0) return memo[end][group];
        double curSum = 0;
        for(int i = end-1; i > 0; i--){
            curSum += A[i];
            memo[end][group] = 
                Math.max(memo[end][group], 
                curSum/(end-i) + search(i, group-1, memo, A));
            
        }
        return memo[end][group];
        
    }