1、动态规划法

我们可以利用数组dp[i][j]dp[i][j]dp[i][j]来表示我们将数组中区间[0,i−1][0,i-1][0,i−1]的元素分为jjj组的平均值的总和。因此我们可以得到状态转化方程如下：{dp[i][j]=∑r=0i−1nums[r]i,j==1dp[i][j]=maxx≥j−1(dp[x][j−1]+∑r=xi−1nums[r]i−x),j>1\left\{\begin{matrix} dp[i][j]= \frac{\textstyle \sum_{r=0}^{i-1}nums[r]}{i} ,j==1 \\ dp[i][j]= \underset{x\ge j-1}{max} (dp[x][j-1]+\frac{\textstyle \sum_{r=x}^{i-1}nums[r]}{i-x}),j>1 \end{matrix}\right. ⎩⎪⎨⎪⎧​dp[i][j]=i∑r=0i−1​nums[r]​,j==1dp[i][j]=x≥j−1max​(dp[x][j−1]+i−x∑r=xi−1​nums[r]​),j>1​
考虑到我们在状态转化方程中会经常使用到区间之和，因此我们可以使用前缀和数组来代替常用的数组。

class Solution {
public:double largestSumOfAverages(vector& nums, int k) {int n = nums.size();vector prefix(n + 1);for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + nums[i];}vector> dp(n + 1, vector(k + 1));for (int i = 1; i <= n; i++) {dp[i][1] = prefix[i] / i;}for (int j = 2; j <= k; j++) {for (int i = j; i <= n; i++) {for (int x = j - 1; x < i; x++) {dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));}}}return dp[n][k];}
};

2、动态规划法优化

由于我们在数组中每次只使用到上一轮的数组，因此我们可以只是用一个一维数组来代替二维数组。

class Solution {
public:double largestSumOfAverages(vector& nums, int k) {int n = nums.size();vector prefix(n + 1);for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + nums[i];}vector dp(n + 1);for (int i = 1; i <= n; i++) {dp[i] = prefix[i] / i;}for (int j = 2; j <= k; j++) {for (int i = n; i >= j; i--) {for (int x = j - 1; x < i; x++) {dp[i] = max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));}}}return dp[n];}
};