最大平均值和的分组 图解题解

这道题到底在问什么

输入

nums=[9,1,2,3,9], k=3

输出

20 （切成 [9],[1,2,3],[9]：9 + 2 + 9）

输入

nums=[1,2,3,4,5,6,7], k=4

输出

20.5

先想最直接的笨办法

记住这套:前缀和算区间平均,dp[i][k] 枚举「第一组切到哪」再加上后面少一组的结果。题面是「最多 k 组」,但本题 nums 是正数,多切一组分数只升不降,最优一定用满 min(k,n)=3 组,所以下面直接按「恰好分 k 组」的 dp[i][k] 来做。（动画第 3 步）

最优解：一步一步想明白

1. 3记住这套:前缀和算区间平均,dp[i][k] 枚举「第一组切到哪」再加上后面少一组的结果。题面是「最多 k 组」,但本题 nums 是正数,多切一组分数只升不降,最优一定用满 min(k,n)=3 组,所以下面直接按「恰好分 k 组」的 dp[i][k] 来做。
2. 4先看原始数据:[9,1,2,3,9]。直觉上两头的 9 自己单独成组最划算,中间的小数挤在一起摊平均。这个直觉待会儿用 DP 来证实。
3. 5把整条数组从左往右累加一遍,得到前缀和数组 s。s[0] 规定为 0,s[1]=9,s[2]=10,一直到 s[5]=24。有了它,任何一段的和都能一减就出来。
4. 6换成前缀和数组看一眼。想求中间 [1,2,3] 这一段的和,直接 s[4] 减 s[1] 等于 6;长度是 3,平均就是 2。不用每次重新加一遍,这就是前缀和省下的功夫。
5. 7再算个整段做对照:全部 5 个数塞进一组,和是 24,平均 4.8。这就是 k=1 时的分数,显然太低。下面正式开填 dp 表,看分多组能拉到多高。
6. 8搭一张表:行是起点 i(从第几个数开始),列是还能分几组 k。右下角灰掉的「无」是元素不够分那么多组的格子,比如最后一个数没法分成 2 组。正数下多切一组分数不降,最优会用满 min(k,n)=3 组,所以这里直接按 exact-k 的 dp[i][k] 填。我们从最左一列 k=1 往右填。
7. 9先填最简单的 k=1 列。只剩一组,意味着从 i 到末尾整段不能再切,分数就是这一整段的平均值。一格一格来。
8. 10从最底下 i=4 开始:只剩一个数 9,自己成一组,平均就是 9。填进 dp[4][1]。
9. 11i=3:剩下 [3,9] 两个数挤一组,和 12、平均 6。填 dp[3][1]=6。
10. 12i=2:剩 [2,3,9] 三个数一组,和 14、平均约 4.67。可以看到一整段塞一起,平均被小数拖下来了。
11. 13i=1:剩 [1,2,3,9] 四个数一组,和 15、平均 3.75。
12. 14i=0:全部 5 个数一组,平均 4.8。k=1 这一列填满了。这些就是「后面只许一组」时各起点的最优,后面分多组要靠它们当地基。
13. 15进入 k=2 列。现在允许切两组:枚举第一组在哪结束,前半段取平均,后半段就是已经算好的 dp[j][1]。注意 i=4 只有一个数,分不出两组,标「无」。
14. 16i=3:剩 [3,9],分两组只有一种切法,第一组 [3]、第二组 [9]。3 加 9 等于 12,比挤一组的 6 整整高了一倍。填 dp[3][2]=12。
15. 17i=2:剩 [2,3,9],两个切点可选。切在 [2] 之后是 2 加 6 等于 8;切在 [2,3] 之后是 2.5 加 9 等于 11.5。取大的 11.5,这意味着把 9 单独留出来更值。
16. 18i=1:剩 [1,2,3,9],三个切点都试。切完 [1] 是 1 加 4.67;切完 [1,2] 是 1.5 加 6;切完 [1,2,3] 是 2 加 9 等于 11,最大。又是把末尾的 9 单独拎出来赢了。dp[1][2]=11。
17. 19i=0 全段分两组,四个切点逐一算:把开头的 9 单独切出来得 12.75;把末尾的 9 单独切出来也是 12.75。两个并列最高,中间那些切法都差一截。
18. 20取最大值 12.75 填进 dp[0][2]。两个并列时代码取先遇到的,也就是切点 j=1、第一组是开头那个 9。k=2 列填满了。
19. 21最后一列 k=3。转移一模一样,只是这次后半段接的是 k=2 那一列的结果。i=3、i=4 元素不够分三组,标「无」。我们要的答案 dp[0][3] 就在这一列最上面。
20. 22i=2:剩 [2,3,9] 分三组,只能每个数各成一组,2 加 3 加 9 等于 14。换个角度:第一组切 [2],后面 [3,9] 正好是刚才算好的 dp[3][2]=12,2 加 12 也是 14,对得上。
21. 23i=1:剩 [1,2,3,9] 分三组。切完 [1] 接 dp[2][2]=11.5 得 12.5;切完 [1,2] 接 dp[3][2]=12 得 13.5,更大。dp[1][3]=13.5。
22. 24到正主了:i=0 全段分三组。把开头 9 单独切出来,后面 [1,2,3,9] 分两组正好是 dp[1][2]=11,9 加 11 等于 20!其它切法都到不了 20。
23. 25取最大值 20 填进 dp[0][3]。这就是「从头开始、最多分三组」的最优分数,也就是题目要的答案。整张表填完了。
24. 26顺着每格当初选的切点回溯一遍:dp[0][3] 选了第一组 [9],跳到 dp[1][2];dp[1][2] 选了第一组 [1,2,3],跳到 dp[4][1];最后 [9] 收尾。三组就是 [9]、[1,2,3]、[9]。
25. 27回到原数组看最终分法:绿色 [9] 一组、蓝色 [1,2,3] 一组、红色 [9] 一组。9 加 2 加 9 等于 20,和 dp 表算出的答案严丝合缝。两头的大数各自独占一组,中间小数摊平,这正是最优。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        @cache
        def dfs(i: int, k: int) -> float:
            if i == n:
                return 0
            if k == 1:
                return (s[n] - s[i]) / (n - i)
            ans = 0
            for j in range(i + 1, n):
                ans = max(ans, (s[j] - s[i]) / (j - i) + dfs(j, k - 1))
            return ans

        n = len(nums)
        s = list(accumulate(nums, initial=0))
        return dfs(0, k)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        int s[n + 1];
        double f[n][k + 1];
        memset(f, 0, sizeof(f));
        s[0] = 0;
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        function<double(int, int)> dfs = [&]( int i, int k ) -> double {
            if (i == n) {
                return 0;
            }
            if (k == 1) {
                return (s[n] - s[i]) * 1.0 / (n - i);
            }
            if (f[i][k] > 0) {
                return f[i][k];
            }
            double ans = 0;
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, (s[j] - s[i]) * 1.0 / (j - i) + dfs(j, k - 1));
            }
            return f[i][k] = ans;
        };
        return dfs(0, k);
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Double[][] f;
    private int[] s;
    private int n;

    public double largestSumOfAverages(int[] nums, int k) {
        n = nums.length;
        s = new int[n + 1];
        f = new Double[n][k + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        return dfs(0, k);
    }

    private double dfs(int i, int k) {
        if (i == n) {
            return 0;
        }
        if (k == 1) {
            return (s[n] - s[i]) * 1.0 / (n - i);
        }
        if (f[i][k] != null) {
            return f[i][k];
        }
        double ans = 0;
        for (int j = i + 1; j < n; ++j) {
            ans = Math.max(ans, (s[j] - s[i]) * 1.0 / (j - i) + dfs(j, k - 1));
        }
        return f[i][k] = ans;
    }
}

复杂度

面试官可能追问