目標(biāo)和
問(wèn)題描述
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) target 厦酬。
向數(shù)組中的每個(gè)整數(shù)前添加 '+' 或 '-' 憾朴，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè) 表達(dá)式 ：
例如焙贷，nums = [2, 1] 缩抡，可以在 2 之前添加 '+' ，在 1 之前添加 '-' 独柑，然后串聯(lián)起來(lái)得到表達(dá)式 "+2-1" 迈窟。
返回可以通過(guò)上述方法構(gòu)造的、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目忌栅。
思路
sum ：是數(shù)組內(nèi)所有元素的總和车酣，
target ：目標(biāo)和
假如 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，我們把問(wèn)題轉(zhuǎn)化一下：即只需要求的 所有 left的組合即可以確定 答案瑞驱。
這就和01背包問(wèn)題類(lèi)似了娘摔，選擇還是不選擇。
特殊情況考慮：
（sum+target）/2 不能是小數(shù)唤反，即必須整除凳寺。
|sum| > |target|
go代碼實(shí)現(xiàn)
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++ {
//每運(yùn)行一遍，覆蓋之前的值
for j := bag; j>=nums[i]; j-- {
dp[j] += dp[j-nums[i]]
}
}
return dp[bag]
}
一和零
問(wèn)題描述
給你一個(gè)二進(jìn)制字符串?dāng)?shù)組 strs 和兩個(gè)整數(shù) m 和 n 彤侍。
請(qǐng)你找出并返回 strs 的最大子集的長(zhǎng)度肠缨，該子集中 最多 有 m 個(gè) 0 和 n 個(gè) 1 。
如果 x 的所有元素也是 y 的元素盏阶，集合 x 是集合 y 的 子集 晒奕。
思路
m: 0的容量
n: 1的容量
這里有兩個(gè)背包，要同時(shí)滿(mǎn)足，需要用二維數(shù)組去保存
1 dp的含義
dp[i][j] : 在最多有i個(gè)0脑慧，j個(gè)1的 子集的最大長(zhǎng)度魄眉，
2 確定遞推規(guī)則
一個(gè)字符中，0有 zsum闷袒，1有osum
dp[i][j] = max (dp[i][j] , dp[i-zsum][j-osum] + 1)
3 初始化dp
dp 初始化為0即可坑律，
4 遍歷順序
從后往前，
5 舉例
霜运。脾歇。。淘捡。
go代碼實(shí)現(xiàn)
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
}
}
