416.分割等和子集
416.分割等和子集
题解
题目：给定一个数组，问能否将该数组分成两个数组，并且这两个数组元素累加值一样
思路：
首先剪枝：
1. 数组元素少于2，肯定不行
2. 数组元素累加和是奇数，肯定不行
3. 元素中最大元素>累加和的一半，肯定不行
那么对于数组来说，只要拼凑出元素和=累加和/2，就行了，一定会存在没有选的元素累加=一半的。
1. 刚开始，想的是递归，只有选和不选，超时 2. 记忆化, AC，但是效率很低
对于自上而下的递归，一般都可以修改为自下而上的动态规划
target=sum/2 因为我们需要元素累加刚好等于target 定义：dp[i][j]前i个元素,累加和j,是否为true 初始：dp[0][nums[0]]=true 状态转移：dp[i][j] = dp[i-1][j] || dp[i-1][j-v] 不选这个元素 || 选这个元素 最终：dp[len(nums)-1][target]
众所周知01背包二位转一维优化空间复杂度 二维数组转一维，滚动数组
代码
func canPartition(nums []int) bool { if len(nums) < 2 { return false } sum, max := 0, 0 for _, v := range nums { sum += v if max < v { max = v } } if sum%2 != 0 { return false } target := sum / 2 if max > target { return false } type pair struct { idx, tot int } mp := make(map[pair]bool) var dfs func(idx, tot int) bool dfs = func(idx, tot int) bool { if tot == target { return true } if tot > target || idx >= len(nums) { return false } p := pair{idx, tot} if _, ok := mp[p]; !ok { mp[p] = dfs(idx+1, tot) || dfs(idx+1, tot+nums[idx]) } else { return mp[p] } return mp[p] } return dfs(0, 0) }
func canPartition(nums []int) bool { if len(nums) < 2 { return false } sum := 0 max := 0 for _, v := range nums { sum += v if max < v { max=v } } if sum%2 != 0 { return false } target := sum / 2 if max > target { return false } dp := make([][]bool, len(nums)) for i := range dp { dp[i] = make([]bool, target+1) } dp[0][nums[0]] = true for i := 1; i < len(nums); i++ { v := nums[i] for j := 1; j <= target; j++ { if j >= v { dp[i][j] = dp[i-1][j] || dp[i-1][j-v] } else { dp[i][j] = dp[i-1][j] } } } return dp[len(nums)-1][target] }
func canPartition(nums []int) bool { if len(nums) < 2 { return false } sum := 0 max := 0 for _, v := range nums { sum += v if max < v { v = max } } if sum%2 != 0 { return false } target := sum / 2 if max > target { return false } dp := make([]bool, target+1) dp[0] = true for i := 0; i < len(nums); i++ { v := nums[i] for j := target; j >= v; j-- { dp[j] = dp[j] || dp[j-v] } } return dp[target] }
