力扣(LeetCode)813. 最大平均值和的分组(C++)

动态规划

本题需要用到前缀和，前缀和需要将下标 $i$ 后移一位，所以我们将状态的下标 $i$ 也后移一位；由于状态转移依赖于 $j-1$ ，我们将 $j$ 的下标后移一位。

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> s(n+1);
        for(int i = 1;i<=n;i++) s[i] = s[i-1] + nums[i-1];
        vector<vector<double>> f(n+1,vector<double>(m+1,-1e9));
        for(int i = 0;i<=m;i++) f[0][i] = 0;//前[1-0]不能分段，均值为0;
        f[0][0] = 0;// [1-0]只能分成0段
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++)
                for(int k = 0;k<=i-1;k++)
                    f[i][j] = max(f[i][j],f[k][j-1]+(double)(s[i]-s[k])/(i-k));
        return f[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1. 时间复杂度 : $O(n^2\times m)$ ， $n$ 是数组长度 ，状态转移的时间复杂度 $O(n^2\times m)$ 。
2. 空间复杂度 : $O(n^2\times m)$ ，所有状态的空间复杂度 $O(n^2\times m)$ 。

AC