继上一篇后续《(29)Go动态规划经典思想-01背包问题》https://www.jianshu.com/p/5c54e32cdd49
问题1：分割等和子集 //
是一个典型的背包问题，从某地方抽取元素，填充某个值
设sum为非空集合所有元素的和，若sum%2==0且其中有部分元素的和等于sum/2，
则剩下元素和必定为sum/2
抽象成背包问题则变成：从非空集合中，选出一定元素，填充sum/2的背包,如下图示：
func min(v1, v2 uint8) uint8 {
if v1 < v2 {
return v1
}
return v2
}
方法1:记忆化搜索
// 时间复杂度O(n^c)
// 空间复杂度O(n*c)
func canPartition(nums []int) bool {
sum := 0
n := len(nums)
for i := 0; i < n; i++ {
sum += nums[i]
}
if sum%2 != 0 {
return false
}
c := sum / 2
// 0代表未计算,1代表已计算且为true,2代表已计算且为false
memo := make([][]uint8, n)
for i := 0; i < n; i++ {
memo[i] = make([]uint8, c+1)
}
return tryPartion(nums, n-1, c, memo)
}
// [0...index]的数字中是否有能否刚好填充容积c的背包
func tryPartion(nums []int, index, c int, memo [][]uint8) (flag bool) {
if index < 0 || c < 0 {
//因为index和c都可能小于0,索引越界,这里只能直接返回,不能给memo赋值
return false
}
if memo[index][c] != 0 {
return memo[index][c] == 1
}
if c == 0 {
flag = true
} else {
// 2种情况,只要有1种成立即可
// 情况1: index位元素不放进c
flag = tryPartion(nums, index-1, c, memo) ||
// 情况1: index位元素放进c
tryPartion(nums, index-1, c-nums[index], memo)
}
// 存储计算结果
if flag {
memo[index][c] = 1
} else {
memo[index][c] = 2
}
return
}
方法2: 动态规划--二维数组
// 时间复杂度:O(n*c)
// 空间复杂度O(n*c)
func canPartition2(nums []int) bool {
n := len(nums)
if n < 2 {
return false
}
sum := 0
for i := 0; i < n; i++ {
sum += nums[i]
}
if sum%2 != 0 {
return false
}
c := sum / 2
// 0代表未计算,1代表已计算且为true,2代表已计算且为false
memo := make([][]uint8, n)
for i := 0; i < n; i++ {
memo[i] = make([]uint8, c+1)
}
// i行的情况:依赖i-1行求值
if nums[0] > c {
return false
} else {
for i := 0; i <= c; i++ {
if i == nums[0] {
memo[0][i] = 1
} else {
memo[0][i] = 2
}
}
}
// 第i行的值依靠i-2行,i行的值存在i-1行
for i := 1; i < n; i++ {
for j := c; j >= 0; j-- {
// 情况1
memo[i][j] = memo[i-1][j]
// 情况2
if j >= nums[i] {
memo[i][j] = min(memo[i][j], memo[i-1][j-nums[i]])
}
}
}
return memo[n-1][c] == 1
}
方法3: 动态规划--一维优化
// 时间复杂度:O(n*c)
// 空间复杂度O(c)
func canPartition3(nums []int) bool {
n := len(nums)
if n < 2 {
return false
}
sum := 0
for i := 0; i < n; i++ {
sum += nums[i]
}
if sum%2 != 0 {
return false
}
c := sum / 2
// true表示刚好填满,false无法刚好填满
memo := make([]bool, c+1)
//0行情况: nums[0]>c,肯定不成立
if nums[0] > c {
return false
} else {
memo[nums[0]] = true
}
for i := 1; i < n; i++ {
for j := c; j >= nums[i]; j-- {
// 2种情况
// 1)不添加nums[i]能不能填满;2)添加nums[i]能不能填满
if memo[j] || memo[j-nums[i]] {
memo[j] = true
}
}
}
return memo[c]
}
1，2，3提交leetcode，通过
有bug欢迎指出
