数组的均值分割——动态规划&剪枝

这道题要分割出两个数组，平均值需要相等，那其实就相当于分出一个有k个元素的数组的平均值和整体数组的平均值相等就可以满足了，也就是 $target / k = sum / n$。

那么 $target = sum * k / n$

所以我们需要求的其实就是不同的 k 对应的和（target）是否等于 sum * k / n

所以定义可达性 DP 数组如下：

dp[k][sum] 代表刚好 k 个数能组成的和有哪些，可知初始值 dp[0][0] = true

这里我们可以从头到尾的扫描每个数，每个数构建一个两层循环，从 k = n 开始向前更新。

为什么是从后向前更新呢？

首先我们要知道，需要构造出 dp[k][sum]，k必须要扫描到了这么多数字才能开始累积。

如果从前往后开始计算，那么就会导致在扫描的数还没达到 k 个的时候意外的把后面的更新。

比如我们现在才扫描第一个数字，1。

dp[1][1] = true => dp[2][dp[1]对应的和 + 1] = true，这显然不合理，因为我们压根还没有 2 个数。

而从后往前就能保证不会有此种问题发生，因为会随着 num 的扫描，一点点向后产生影响。

比如扫描第一个数字 dp[2][dp[1]对应的和 + 1]（这个时候 dp[1] 是空的所以不会更新），而 dp[1][dp[0] + 1] 有对应的和，所以会更新。

这样一来，就能保证对应的 k 的和一定是可达的。

然后有了这个 dp 数组，一切就很简单了，我们只需要遍历 k 从 1 到 n，其中 $target = sum * k / n$（必须整除），dp[k][target] 等于 true 就说明是可以满足题意的。

于是得到代码如下：

```go
func splitArraySameAverage(nums []int) bool {
    n := len(nums)
    sum := 0
    for _, v := range nums {
        sum += v
    }
    isPossible := false
    for k := 1; k < n; k++ {
        if (sum * k) % n == 0 {
            isPossible = true
            break
        }
    }
    if !isPossible {
        return false
    }
    dp := make([]map[int]bool, n+1)
    for i := range dp {
        dp[i] = make(map[int]bool)
    }
    dp[0][0] = true
    for _, num := range nums {
        for k := n-1; k >= 0; k-- {
            for s := range dp[k] {
                dp[k+1][s+num] = true
            }
        }
    }
    for k := 1; k < n; k++ {
        if sum * k % n != 0 {
            continue
        }
        target := sum * k / n
        if dp[k][target] {
            return true
        }
    }
    return false
}
```

Last modification：July 13, 2025