算法随想录第四十三天打卡|1049. 最后一块石头的重量 II ，494. 目标和 ，474.一和零

 494. 目标和 

大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。  

视频讲解：动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和_哔哩哔哩_bilibili

代码随想录

回溯法

class Solution(object):def findTargetSumWays(self, nums, target):total=sum(nums)if total<target:return 0if (total+target)%2!=0:return 0result=[]target=(total+target)//2nums.sort()self.backtracking(nums,target,0,0,[],result)return len(result)def backtracking(self,nums,target,startindex,total,path,result):if total==target:result.append(path[:])for i in range(startindex,len(nums)):if total+nums[i]>target:breaktotal+=nums[i]path.append(nums[i])self.backtracking(nums,target,i+1,total,path,result)total-=nums[i]path.pop()

总结

我想先用回溯法练练手，因为回溯的路径只能保存加法或减法的数组，所以不知道如何相加。但答案直接是先令都为加，再在这上面进行减的操作，把一个加改成减相当于减去两倍的数，所以把target变成平均数。

01背包法

class Solution(object):def findTargetSumWays(self, nums, target):total=sum(nums)if total<abs(target):return 0if (total+target)%2==1:return 0target_sum=(total+target)//2dp=[0]*(target_sum+1)dp[0]=1for num in nums:for j in range(target_sum,num-1,-1):dp[j]+=dp[j-num]return dp[target_sum]

总结

dp[0]=1我是想不到的，原来初始化也有难的。这里的target也是求得平均值，感觉01背包也不能算减法，这里的背包即是价值也是体积，跟上一题一样。abs函数代表的是绝对值。

01背包法

class Solution(object):def findMaxForm(self, strs, m, n):dp = [[0] * (n + 1) for _ in range(m + 1)]for num in strs:zeroNum = num.count('0')  # 统计0的个数oneNum = len(num) - zeroNum  # 统计1的个数for i in range(m,zeroNum-1,-1):for j in range(n,oneNum-1,-1):dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1) return dp[m][n] 

总结

初始化对了，公式对了，遍历对了，dp数组错了。我之前用了这么久的 dp=[[0]*(n+1)]*(m+1)都没有问题，结果这题就出了问题，明明和 dp = [[0] * (n + 1) for _ in range(m + 1)]得出来的列表都是一样的。