LeetCode_动态规划_中等_813.最大平均值和的分组

冷不防 2023-10-07 19:53 10阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

**示例 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

**提示：**  
1 <= nums.length <= 100  
1 <= nums\[i\] <= 104  
1 <= k <= nums.length

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/largest-sum-of-averages

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

具体细节可见下方代码中的注释。

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public double largestSumOfAverages(int[] nums, int K) {
        
            int length = nums.length;
            //前缀和数组 preSum 记录 nums[0..i - 1] 的累加和
            double[] preSum = new double[length + 1];
            for (int i = 1; i < length + 1; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            // dp[i][k] 表示将数组 nums[0...i - 1] 分成 k 个相邻的非空子数组得到的最大平均值和
            double[][] dp = new double[length + 1][K + 1];
            //初始化 dp
            for (int i = 1; i < length + 1; i++) {
        
                // preSum[i] 为 nums[0...i - 1] 的累加和，preSum[i] / i 即为 nums[0...i - 1] 的元素和的平均值
                dp[i][1] = preSum[i] / i;
            }
            for (int k = 2; k <= K; k++) {
        
                for (int i = 1; i < length + 1; i++) {
        
                    for (int j = 1; j < i; j++) {
        
                        /* 
                        	(1) dp[j][k - 1] 表示将 nums[0...j - 1] 分成 k - 1 份的最大平均值和
                        	(2) (preSum[i] - preSum[j]) / (i - j) 表示 nums[j...i - 1] 的元素和的平均值
                        	(3) dp[j][k - 1] + (preSum[i] - preSum[j]) / (i - j) 即表示将 nums[0...i - 1] 分成 k 份的最大平均值和
                        	(4) 枚举所有可能的 j，然后用 dp[i][k] 保存将 nums[0...i - 1] 分成 k 份的最大平均值和即可
                        */
                        dp[i][k] = Math.max(dp[i][k], dp[j][k - 1] + (preSum[i] - preSum[j]) / (i - j));
                    }
                }
            }
            return dp[length][K];
        }
    }
    
    //空间复杂度优化
    class Solution {
        
        public double largestSumOfAverages(int[] nums, int K) {
        
            int length = nums.length;
            //前缀和数组 preSum 记录 nums[0..i - 1] 的累加和
            double[] preSum = new double[length + 1];
            for (int i = 1; i < length + 1; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            // dp[i] 表示将数组 nums[i...nums.length - 1] 分成 K 个相邻的非空子数组得到的最大平均值和
            double[] dp = new double[length];
            //初始化 dp
            for (int i = 0; i < length; i++) {
        
                // preSum[length] - preSum[i] 为 nums[i...length - 1] 的累加和
                dp[i] = (preSum[length] - preSum[i]) / (length - i);
            }
            for (int k = 0; k < K - 1; k++) {
        
                for (int i = 0; i < length; i++) {
        
                    for (int j = i + 1; j < length; j++) {
        
                        dp[i] = Math.max(dp[i], dp[j] + (preSum[j] - preSum[i]) / (j - i));
                    }
                }
            }
            return dp[0];
        }
    }

[Link 1]: https://leetcode.cn/problems/largest-sum-of-averages/solution/zui-da-ping-jun-zhi-he-de-fen-zu-by-leetcode/