题目描述

给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。输入描述第一行输入m接着输入m个数，表示此数组nums数据范围:1<=m<=50,1<=nums[i]<=50

输出描述

最小拆分数组和

用例

输入

7

4 3 2 3 5 2 1

输出

5

说明

可以等分的情况有：4个子集(5),(1,4), (2,3), (2,3)；

2个子集(5,1,4),(2,3,2,3)但最小的为5。

解题思路

这个题可以用回溯法或者动态规划, 回溯法时间复杂度太高, 可达O(sqrt(sum(nums))*2^m), 超过2^50的时间, 太慢了!

可以用动态规划来优化:

1. 先把所有数求和得到一个sum, 对这个sum进行因子分解, 分解成k 个 相同的子数组, 每个子数组的和都是x
2. 利用动态规划从小到大对因子x检查是否可以分成k个和为x的因子, 且k*x=sum

代码实现

package main

import "sort"

/*
给定一个数组nums,将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值

输入描述： 第一行输入 m 接着输入m个数，表示此数组 数据范围:1<=M<=50, 1<=nums[i]<=50
输出描述：
最小拆分数组和。

示例：
输入：
7 4 3 2 3 5 2 1
输出：
5

说明：可以等分的情况有：
4 个子集（5），（1,4），（2,3），（2,3）
2 个子集（5, 1, 4），（2,3, 2,3）
但最小的为5。

动态规划
定义状态 $dp[i][j]$ 表示前 $i$ 个数能否分成 $j$ 个都为因子的子数组
*/
func canSplit(nums []int, k int, x int) bool {
	n := len(nums)
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, k+1)
	}

	// 初始化状态
	for i := 1; i <= n; i++ {
		dp[i][1] = dp[i-1][1] || nums[i-1] == x
	}

	// 状态转移
	for i := 2; i <= n; i++ {
		for j := 2; j <= k; j++ {
			for l := i - 1; l >= j-1; l-- {
				if dp[l][j-1] && sum(nums[l:i]) == x {
					dp[i][j] = true
					break
				}
			}
		}
	}

	return dp[n][k]
}

/*
因子分解+动态规划
*/
func minSum(nums []int) int {
	s := sum(nums)
	m := len(nums)
	factors := []int{}
	for i := 1; i*i <= s; i++ {
		if s%i == 0 {
			factors = append(factors, i)
			if i != s/i {
				factors = append(factors, s/i)
			}
		}
	}
	sort.Ints(factors)
	// 对所有因子进行遍历，计算是否能够分成 k 个都为 factor 的子数组
	minSum := s
	for _, factor := range factors {
		k := s / factor
		if k < 2 {
			continue
		}

		dp := make([][]bool, m+1)
		for i := range dp {
			dp[i] = make([]bool, k+1)
		}
		dp[0][0] = true

		for i := 1; i <= m; i++ {
			for j := 1; j <= k; j++ {
				if nums[i-1] > factor {
					dp[i][j] = false
				} else if nums[i-1] == factor {
					dp[i][j] = dp[i-1][j-1]
				} else {
					/*
					   我们可以分为两种情况来考虑：

					   不选第 $i$ 个物品，此时背包的容量仍然是 $j$，因此选法和 $dp[i-1][j]$ 相同。
					   选第 $i$ 个物品，此时背包的容量为 $j-1$，因此选法和 $dp[i-1][j-1]$ 相同。
					   由于我们只需要判断是否存在一种选法，使得背包被恰好填满，因此可以使用逻辑或运算符将这两种情况合并起来，即：
					   dp[i][j]=dp[i−1][j−1] ∣∣ dp[i−1][j]
					*/
					dp[i][j] = dp[i-1][j-1] || dp[i-1][j]
				}
			}
		}

		if dp[m][k] {
			minSum = factor
			break
		}
	}
	return minSum
}

时间复杂度分析

因子个数是O(sqrt(sum(nums))), 总时间复杂度是 O(sqrt(sum(nums))* m^2)