动态规划

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

class Solution {
public:double largestSumOfAverages(vector& nums, int m) {int n = nums.size();vector s(n+1);for(int i = 1;i<=n;i++) s[i] = s[i-1] + nums[i-1];vector> f(n+1,vector(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. 时间复杂度 : O(n2×m)O(n^2\times m)O(n2×m) ， nnn 是数组长度 ，状态转移的时间复杂度 O(n2×m)O(n^2\times m)O(n2×m) 。
2. 空间复杂度 : O(n2×m)O(n^2\times m)O(n2×m) ，所有状态的空间复杂度 O(n2×m)O(n^2\times m)O(n2×m) 。

AC