Blog

leetcode813最大平均值和的分组

leetcode813 Largest Sum of Averages

Posted by BY on May 28, 2018

前言

动规、归在中等类，但是比较难吧

正文

问题来源

本问题来自leetcode上的813题。这道题自己并没能独立解出来，参考网上的博文。Leetcode 813

问题描述

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]  
输出: 15  
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

分析：

当看到Note里面A的lenth最大值是100的时候,这道题如果用dfs的话可能会超时(没有去试),用dp的话目测应该需要三重循环,因此此时大概就会想到用dp[k][i]表示前i+1个元素(0~i)最多分k个组是平均数和最大,然后就是自己手动写一个表可以简单推导一下.表格如下:

k\i 0 1 2 3 4
0 9 5 4 3.75 4.8
0 9 10 10.5 11 12.75
0 9 10 12 13.5 20

自己认认真真打完表后很容易就可以dp的方程:
dp[k][i] = Math.max(dp[k - 1][i], dp[k - 1][j] + (sum[j + 1, i] / (i - j)); (k > = 1, sum[j + 1, i]表示区间j+1到i中间所有数的和)
当然求区间和的话我们可以做一下预处理保证sum[j+1,i]是O(1)时间就可以
C代码如下：

#define max(x,y) ((x)>(y)?(x) : (y))
double largestSumOfAverages(int* A, int ASize, int K) {
    double **dp = NULL;
	int i,j,k;
	double ret,temp;
	int *sum;
	dp = (double**)malloc((K)*sizeof(double*));
	for(i=0;i<K;i++)
	{
		dp[i] = (int*)malloc(ASize*sizeof(double));
	}
	sum = (int*)malloc(ASize*sizeof(int));
	sum[0] = A[0];
	dp[0][0] = A[0];
	for(i=1;i<ASize;i++)
	{
		sum[i] = sum[i-1] + A[i];
		dp[0][i] = sum[i] / (double)(i+1);
	}

	for(i=1;i<K;i++)
	{
		//dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);
		for(j=0;j<ASize;j++)
		{
			temp = dp[i-1][j];
			for(k=0;k<j;k++)
			{
				temp = max(temp,dp[i-1][k]+(sum[j]-sum[k])/(double)(j-k));
			}
			dp[i][j] = temp;
		}
	}
	ret = dp[K-1][ASize-1];
	for(i=0;i<K;i++)
	{
		free(dp[i]);
	}
	free(dp);
	free(sum);
	dp = NULL;
	return ret;
}

Java

class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int len = A.length;
        double[] pre = new double[len + 1]; //区间和预处理 sum[i, j] = pre[j + 1] - pre[i]
        for (int i = 1; i <= len; ++i) {
            pre[i] = pre[i - 1] + A[i - 1];
        }
        double[][] dp = new double[K][len];
        for (int k = 0; k < K; ++k) {
            for (int i = 0; i < len; ++i) {
                dp[k][i] = k == 0 ? pre[i + 1]/(i + 1) : dp[k - 1][i];
                if (k > 0) {
                    for (int j = i - 1; j >= 0; --j) {
                        dp[k][i] = Math.max(dp[k][i], dp[k - 1][j] + (pre[i + 1] - pre[j + 1]) / (i - j));
                    }
                }
            }
        }
        return dp[K - 1][len - 1];
    }
}

总结：

目前讨论区中仅仅只有DFS和时间复杂度为O(KNN)的解法。

结语

闲来无事的话，多练习练习，做做题。

CATALOG
    FEATURED TAGS
    Blog