leetcode.813 最大平均值和的分组 - 前缀和 + dp

​​​​​​813. 最大平均值和的分组

思路：

一个简单的数学结论：

划分份数越多，平均值之和越大，因此想要取得最大值必然是恰好划分成 k 份

• 用 dp[i][j]" role="presentation">dp[i][j]$dp[i][j]$ 表示 前i个元素划分成j份的最大平均和，则答案就是 dp[n][k]" role="presentation">dp[n][k]$dp[n][k]$
• 当 j=1" role="presentation">j=1$j=1$ 时，dp[i][j]" role="presentation">dp[i][j]$dp[i][j]$ 就是 [0,i−1]" role="presentation">[0,i−1]$[0,i-1]$ 元素的平均值
• 当 j>1" role="presentation">j>1$j>1$ 时，我们可以把区间 [0,i−1]" role="presentation">[0,i−1]$[0,i-1]$ 划分成 [0,x−1]" role="presentation">[0,x−1]$[0,x-1]$ 和 [x,i−1]" role="presentation">[x,i−1]$[x,i-1]$ 两部分，dp[i][j]" role="presentation">dp[i][j]$dp[i][j]$ 等于所有这些合法的切分方式的平均值和的最大值
• 所以状态转移方程就是

• dp[i][j]=max(dp[i][j],dp[x][j-1]+(s[i]-s[x])/(i-x));
  

其中 dp[x][j - 1] + (s[i] - s[x]) / (i - x) 表示为 x 位置 之前的最大值分组和 + 当前位置平均值

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) 
    {
        int n = nums.size();
        vector<double> s(n+1);
        for(int i=0;i1]=s[i]+nums[i];
        vectordouble>> dp(n+1,vector<double>(k+1));
 
        for(int i=1;i<=n;i++) dp[i][1]=s[i]/i;
 
        for(int j=2;j<=k;j++) //枚举分组数
            for(int i=j;i<=n;i++) //枚举分组元素
                for(int x=j-1;x//枚举分割位置
                    dp[i][j]=max(dp[i][j],dp[x][j-1]+(s[i]-s[x])/(i-x));
        return dp[n][k];
    }
};