LeetCode-813-最大平均值和的分组

1、动态规划法

我们可以利用数组$dp[i][j]$来表示我们将数组中区间$[0,i-1]$的元素分为$j$组的平均值的总和。因此我们可以得到状态转化方程如下： { d p [ i ] [ j ] = ∑ r = 0 i − 1 n u m s [ r ] i , j = = 1 d p [ i ] [ j ] = m a x x ≥ j − 1 ( d p [ x ] [ j − 1 ] + ∑ r = x i − 1 n u m s [ r ] i − x ) , j > 1 \left\{

\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<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        vector<vector<double>> dp(n + 1, vector<double>(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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、动态规划法优化

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

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        vector<double> 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22