代码随想录补打卡 1049. 最后一块石头的重量 II494 目标和 474 1和0
标签： 代码随想录补打卡 1049. 最后一块石头的重量 II494 目标和 474 1和0
2023-05-18 18:23:27 219浏览
代码如下
func lastStoneWeightII(stones []int) int { //思路和分割子集差不多，就是把石头分成两堆，并且使两堆的差尽可能的小
sum := 0
for i := 0 ; i < len(stones) ; i++ {
sum += stones[i]
}
target := sum/2
dp := make([]int,1501)
for i := 0 ; i < len(stones) ; i++ {
for j := target ; j >= stones[i] ;j-- { //dp[j] 表示当前容量下，最大价值
dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])
}
}
return sum - (2*dp[target])
}
func max(a,b int) int{
if a > b {
return a
}else {
return b
}
}
494 目标和
代码如下
func findTargetSumWays(nums []int, target int) int {
sum := 0
for i := 0 ; i < len(nums) ; i++ {
sum += nums[i]
}
if (sum+target) % 2 == 1 {
return 0
}
if abs(target) > sum {
return 0
}
left := (sum+target)/2
dp := make([]int,left+1)
dp[0] = 1 //如果这个dp[0]的初始值是0的话，那么所有值都会变为0
for i := 0 ; i < len(nums) ; i++ {
for j := left ; j >= nums[i] ; j-- { //这里为什么要从后往前遍历，是因为， dp[j] += dp[j-nums[i]] 可以写成 dp[j] = dp[j] + dp[j-nums[i]] 。举例来说当dp[4] 要放入元素1 时，那么他有两种选择，一种是放入元素1 ，一种是不放元素1 。在不放元素1的情况下，装满dp[4]的方法共有上一个dp[4]种方法。而要放入元素1的话。那么就有dp[3]种方法，再放入1就可以装满dp[4]，所以总共有的方法是上一层的dp[3]+dp[4] 。所以可以看出dp[j]的取值是源于之前值的计算，但是如果采用从前向后遍历，在遍历到dp[4]的时候，dp[3]的值已经被更新，那么显然结果就不正确了。
dp[j] += dp[j-nums[i]] //递推关系是为什么是这个，原因是，假设背包容量为4，装满要dp[4]种方法。那么一共有这样几种情况，一种是4+dp[0]即之前已经装满了dp[0]，这时候只要一个4就装满了。第二种是3+dp[1]即，之前只要装满dp[1]在装入3 ，同理还有2+dp[2] 和 1+dp[3] 那么要装满dp[4]的方法总共有dp[0]+dp[1]+dp[2]+dp[3]种方法。 dp[j] += dp[j-nums[i]] 这个递推关系式会依次放入1,2,3,4 四个元素
}
}
return dp[left]
}
func abs(a int) int{
if a > 0 {
return a
}else {
return a*(-1)
}
}
474 1和0
代码如下
func findMaxForm(strs []string, m int, n int) int {
dp := make([][]int,m+1)
for i, _ := range dp { //创建一个二维的dp数组
dp[i] = make([]int,n+1)
}
for i := 0 ; i < len(strs) ; i++ { 遍历字符串
x,y := 0,0 //x表示0的个数，y表示1的个数
for _,v := range strs[i] { 遍历字符串里第i个字符，并统计这个字符的0和1的个数
if v == '0' {
x++
}else{
y++
}
}
for j := m ; j >= x ; j-- { //遍历背包容量，看这个背包可不可以放入这个字符，背包有两个维度即0和1
for k := n ; k >= y ; k-- {
dp[j][k] = max(dp[j][k],dp[j-x][k-y]+1) //这里背包有两种选择一种是放入这个元素，一种是不放入这个元素，如果不放入这个元素，那么他的数量还是和之前的一样，如果要放入这个元素，那么就要先减去x，y这两个元素，然后再将含有x，y的元素放入
}
}
}
return dp[m][n]
}
func max(a,b int) int {
if a > b {
return a
}else {
return b
}
}
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
