Problem: 813. 最大平均值和的分组
文章目录
- 思路
- 解题方法
- Code
思路
首先由于子数组内是连续的，可以用前缀和先把和求出来，再利用perSum[j] -perSum[i-1]来求子数组的和，进而得到区间分组的平均值。现在最大的问题是分组，怎么分组([0,k]) ? 我们将大问题分解成k个小问题，大问题是如何将给定数组 nums 分成最多 k 个非空连续子数组，以使得这些子数组的平均值之和最大。小问题可以定义为：从数组的某个特定起点 i 开始，将数组的剩余部分（nums[i] 到 nums[n-1]）分成最多 j 个连续子数组，以使得这些子数组的平均值之和最大，其中 j ≤ k。
解题方法
- 计算前缀和
我们首先计算数组 nums 的前缀和数组perSum。对于数组中的每个元素 nums[i]，perSum[i] 存储从 nums[0] 到 nums[i] 的总和。 - 定义记忆化数组
使用一个二维数组 f 来存储已经解决的子问题的结果。这里f[i][j]表示从第 i 个元素开始，将数组剩余部分分成 j 组所能获得的最大分数。如果一个子问题已经被解决，我们可以直接从 f 中取得结果，而无需重新计算。 - 编写dfs函数
递归函数dfs(i, k)计算从索引 i 开始，将数组剩余部分分成 k 组所能获得的最大分数。 如果我们到达数组的末尾（即 i == n），则返回 0，因为没有剩余元素可以分组。 如果只剩下一组（即 k == 1），则直接返回从 i 到数组末尾的所有元素的平均值。 如果f[i][k]已经有值，则直接返回该值，表示这个子问题已经被解决。 否则，我们遍历所有可能的分割点，计算将数组分成两部分（当前部分和剩余部分）所能获得的最大分数，并更新f[i][k]。
Code
class Solution {
public:
// dfs 将问题规模缩小，dfs(i,k) 表示在当前位置i到n ，划分成k个分组的平均值
double dfs(vector<int> &perSum , int i , int k , int n ,vector<vector<double>>& f ) {
// 已经分完了，返回0
if(i == n) return 0 ;
// 当前只剩下一组了，就返回它，从当前[i,n]的平均值
if(k == 1 ) return (perSum[n] - perSum[i] ) *1.0/ (n-i);
if(f[i][k] > 0 ) return f[i][k] ;
double ans = 0.0 ;
for(int j = i ; j< n ; j++) {
// 本组选取了[i,j]区间的平均值 + 下一个组应该是从[j,n]继续分组
double t = (perSum[j+1] - perSum[i])*1.0/ (j-i+1) + dfs(perSum , j+1,k-1,n,f) ;
ans = max(ans, t) ;
}
f[i][k] = ans ;
return ans ;
}
double largestSumOfAverages(vector<int>& nums, int k) {
int n = nums.size() ;
vector<int> s(n+1) ;
// f函数用来存储记忆化搜索结果，前i个元素并且分成 j个组时的最大平均值
vector<vector<double>> f(n,vector<double>(k+1,0)) ;
for(int i = 0 ; i<n ; i++ ) s[i+1] = s[i] + nums[i] ;
return dfs(s,0,k,n,f) ;
}
};