Leecode 813. 最大平均值和的分组 DP

原题链接：Leecode 813. 最大平均值和的分组

参考题解：Leecode 813. 最大平均值和的分组 动态规划详解

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