目标和
问题描述
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路
sum ：是数组内所有元素的总和，
target ：目标和
假如 left - right =target 。即存在此情况
left ： 所有前面为+的元素的和
right ： 所有前面为- 的元素的和
列出等式：
等式1 ： left + right =sum
等式2 ： left - right = target
由等式1 和等式2 可以得出：
等式3 ： left = （sum+target）/2
由于sum 和 target 是固定的，所以left和right也是固定的。
OK，我们把问题转化一下：即只需要求的 所有 left的组合即可以确定 答案。
这就和01背包问题类似了，选择还是不选择。
特殊情况考虑：
（sum+target）/2 不能是小数，即必须整除。
|sum| > |target|
go代码实现
func findTargetSumWays(nums []int, target int) int {
sum :=0
for _, v := range nums {
sum+=v
}
//考虑特殊情况
if target >sum || (sum+target)<0 { return 0}
if (sum+target)%2 == 1 { return 0}
//背包容量就是left
bag := (sum+target)/2
dp := make([]int,bag+1)
//这里初始化为1
dp[0] =1
for i:=0; i<len(nums) ; i++ {
//每运行一遍，覆盖之前的值
for j := bag; j>=nums[i]; j-- {
dp[j] += dp[j-nums[i]]
}
}
return dp[bag]
}
一和零
问题描述
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路
m: 0的容量
n: 1的容量
这里有两个背包，要同时满足，需要用二维数组去保存
1 dp的含义
dp[i][j] : 在最多有i个0，j个1的 子集的最大长度，
2 确定递推规则
一个字符中，0有 zsum，1有osum
dp[i][j] = max (dp[i][j] , dp[i-zsum][j-osum] + 1)
3 初始化dp
dp 初始化为0即可，
4 遍历顺序
从后往前，
5 举例
。。。。
go代码实现
func findMaxForm(strs []string, m int, n int) int {
dp := make([][]int,m+1)
for i,_ := range dp {
dp[i] = make([]int,n+1)
}
for i:=0;i<len(strs);i++ {
zsum, osum:= 0,0
for _,v := range strs[i] {
if v == '0'{
zsum+=1
} else {
osum+=1
}
}
for j:=m; j>=zsum; j-- {
for k:=n; k>=osum; k-- {
dp[j][k] = max(dp[j][k],dp[j-zsum][k-osum]+1)
}
}
}
return dp[m][n]
}
func max(a,b int) int {
if a>b {
return a
} else {
return b
}
}
