func max(a, b int) int {
if a > b {
return a
}
return b
}
//1049. 最后一块石头的重量 II
func lastStoneWeightII(stones []int) int {
sum := 0
n := len(stones)
for i := 0; i < n; i++ {
sum += stones[i]
}
mid := sum / 2
dp := make([]int, mid+1)
for i := 0; i < n; i++ {
///这里必须倒序
for j := mid; j >= stones[i]; j-- {
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
}
}
return sum - dp[mid] - dp[mid]
}
//494. 目标和
func findTargetSumWays(nums []int, target int) int {
sum := 0
n := len(nums)
for i := 0; i < n; i++ {
sum += nums[i]
}
//如果是奇数肯定无法得到目标值，直接返回0
if (sum+target)%2 != 0 {
return 0
}
if target < 0 {
target = -target
}
if target > sum {
return 0
}
left := (sum + target) / 2
dp := make([]int, left+1)
dp[0] = 1
for i := 0; i < n; i++ {
for j := left; j >= nums[i]; j-- {
dp[j] += dp[j-nums[i]]
}
}
return dp[left]
}
//474. 一和零
func findMaxForm(strs []string, m int, n int) int {
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
for i := 0; i < len(strs); i++ {
zeroNum := 0
for _, v := range strs[i] {
//先统计每个字符串0的数量
if v == '0' {
zeroNum++
}
}
//在计算1的数量
oneNum := len(strs[i]) - zeroNum
for j := m; j >= zeroNum; j-- {
for k := n; k >= oneNum; k-- {
dp[j][k] = max(dp[j][k], dp[j-zeroNum][k-oneNum]+1)
}
}
}
return dp[m][n]
}