leetcode 813. Largest Sum of Averages 最大平均值和的分组-耗时91%

Problem: 813. Largest Sum of Averages 最大平均值和的分组

解题过程

使用了动态规划的，耗时91%，若只使用回溯情况太多肯定会超时而且不好控制回溯的步长，所以考虑使用动态规划，存在两个变量，一个是K，另一个是数组长度n，所以动态规划的数组使用dp[k+1][n+1]，vector<vector> dp(k+1, vector(n+1, 0.0));

首先计算数组的前缀和prefixSum，当k=1时，不论数组多长，都是取平均值，dp[1][j] = prefixSum[j] / (double)j;，然后双重循环，i是k的取值，j是数组长度，若i>=j也就是数组长度更短，此时每个数字单独做一组，累加也就是前缀和，if(j <= i) dp[i][j] = prefixSum[j];

若i<j，数组更长的，此时考虑将数组分成两部分，前一部分划分k-1次，最后一部分单独做1次，共k次，前一部分的最大值是dp[i-1][w]，后一部分则是平均值(prefixSum[j] - prefixSum[w]) / (double)(j - w);，两者相加即可，最后拿到最大值就行

double mx = INT_MIN, tmp; for(int w = i - 1; w < j; w++) { tmp = dp[i-1][w] + (prefixSum[j] - prefixSum[w]) / (double)(j - w); if(mx < tmp) { mx = tmp; } } dp[i][j] = mx;

Code

class Solution { public: double largestSumOfAverages(vector<int>& nums, int k) { vector<int> prefixSum={0}; int s = 0; for(int& i : nums) { s += i; prefixSum.push_back(s); } int n = nums.size(); vector<vector<double>> dp(k+1, vector<double>(n+1, 0.0)); for(int j = 1; j <= n; j++) { dp[1][j] = prefixSum[j] / (double)j; } for(int i = 2; i <= k; i++) { for(int j = 1; j <= n; j++) { if(j <= i) { dp[i][j] = prefixSum[j]; } else { double mx = INT_MIN, tmp; for(int w = i - 1; w < j; w++) { tmp = dp[i-1][w] + (prefixSum[j] - prefixSum[w]) / (double)(j - w); if(mx < tmp) { mx = tmp; } } dp[i][j] = mx; } } } return dp[k][n]; } };