标签：分数 nums 力扣 prefix 分组 813 leetcode dp size

问题描述

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。

注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。

返回我们所能得到的最大 分数 是多少。答案误差在 10^-6 内被视为是正确的。

提示:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 104
• 1 <= k <= nums.length

示例

示例 1:

输入: nums = [9,1,2,3,9], k = 3
输出: 20.00000
解释: 
nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. 
我们也可以把 nums 分成[9, 1], [2], [3, 9]. 
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.

示例 2:

输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000

解题思路

这题首先要明白的是，将原数组 nums 分为 k 个子数组，一定可以取得最大分数。假设有两个数 a 和 b ，只要 \(a \not= b\) 且 a,b > 0 ,就会存在 a + b >= (a + b) / 2。因此，分组之后的和不小于不分组的和，为了简化代码，我们就假设进行 k 个分组。

在明确了 k 个分组后，我们就能想到动态规划，假设之前已经分了 k - 1 个分组，那么我们只要找到最后一个分组时的起始位置即可计算 分数 。

当只有一个分组时， dp[i][1] 表示 nums 中前 i 个元素的平均值。

当有多个分组时，令 dp[i][j - 1] 表示将 nums 前 i 个元素划分为 j-1 个分组， i > j >= 1 。 因此， dp[i][j] 可以按以下方式计算：

\[ dp[i][j]= \begin{cases} {\frac{\sum_{k=1}^i nums[k]}{i}, \quad {j=1}} \\ {max(dp[n][j-1] + \frac{\sum_{k=n}^{i} nums[k]}{i - n}, \quad {j>1}} \end{cases}\]

按照状态转移方程，实现如下代码：

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        vector<vector<double>> dp(nums.size(), vector<double>(k));
        vector<int> prefix(nums.size());
        dp[0][0] = nums[0];
        prefix[0] = nums[0];
        double tmp;
        for(int i = 1; i < nums.size(); i++){
            prefix[i] = nums[i] + prefix[i - 1];
            dp[i][0] = (prefix[i]) / (i + 1.0);
        }
        for(int i = 1; i < nums.size(); i++){
            for(int j = 1; j <= i && j < k; j++){
                for(int n = i - 1; n >= j - 1; n--){
                    tmp = dp[n][j - 1] + (static_cast<double>(prefix[i] - prefix[n])) / (i - n);
                    dp[i][j] = dp[i][j] > tmp ? dp[i][j] : tmp;
                }
            }
        }
        return dp[nums.size() - 1][k - 1];
    }
};

标签：分数,nums,力扣,prefix,分组,813,leetcode,dp,size
From： https://www.cnblogs.com/greatestchen/p/16933492.html