动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和-动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和

热门回复：

• BBGG丶狮孒喵:这道题感觉没讲清楚呀。。建议不懂的同学自己先用二维数组来做，比较好理解，理解了之后再用一维数组。 1. 含义：dp【i】【j】：从下标为【0...i】的物品里任取，填满j这么⼤容积的包，有dp【i】【j】种⽅法 2. 递推式：dp【i】【j】 = dp【i-1】【j】 + dp【i-1】[j-nums【i】] dp【i-1】【j】是不将物品i放入背包的方式数，dp【i-1】[j-nums【i】]是将物品i放入背包的方式数 3. 初始化：dp【0】【0】 = 1 表示装满容量为0的背包，有1种⽅法，就是装0件物品。 如果nums【0】在范围内的话，dp【0】[nums【0】] = 1 其他全为0 4. 计算顺序：顺序，行优先
• 左耳朵000:这题讲的好乱呀
• 咿呀搞事情:这里，我们可以把状态定义为dp【i】【j】，表示用数组中前i个元素组成和为j的方案数。那么状态转移方程就是： dp【i】【j】 = dp【i-1】[j-nums【i】] + dp【i-1】[j+nums【i】] 这个方程的意思是，如果我们要用前i个元素组成和为j的方案数，那么有两种选择：第i个元素取正号或者取负号。如果取正号，那么前i-1个元素就要组成和为j-nums【i】的方案数；如果取负号，那么前i-1个元素就要组成和为j+nums【i】的方案数。所以两种选择的方案数相加就是dp【i】【j】。 但是这样定义状态会导致空间复杂度过高，因为我们需要一个二维数组来存储所有可能的状态。所以我们可以对问题进行一些变换，把它转化为一个背包问题。 我们可以把数组中所有取正号的元素看作一个集合P，所有取负号的元素看作一个集合N。那么有： sum(P) - sum(N) = target sum(P) + sum(N) = sum(nums) 两式相加得： sum(P) = (target + sum(nums)) / 2 也就是说，我们只需要找到有多少种方法可以从数组中选出若干个元素使得它们的和等于(target + sum(nums)) / 2即可。这就变成了一个经典的01背包问题。 所以我们可以把状态定义为dp【j】，表示用数组中若干个元素组成和为j的方案数。那么状态转移方程就是： dp【j】 = dp【j】 + dp[j - nums【i】] 这个方程的意思是，如果我们要用若干个元素组成和为j的方案数，那么有两种选择：不选第i个元素或者选第i个元素。如果不选第i个元素，那么原来已经有多少种方案数就不变；如果选第i个元素，那么剩下要组成和为j - nums【i】 的方案数就等于dp[j - nums【i】]。所以两种选择相加就是dp【j】。 但是在实现这个状态转移方程时，有一个细节需要注意：由于每次更新dp【j】都依赖于之前计算过得dp值（也就是说当前行依赖于上一行），所以我们必须从后往前遍历更新dp值（也就是说从右往左更新），否则会覆盖掉之前需要用到得值。 最后返回dp【bag_size】即可。
• TinaisIT:自从变成一维听得就稀里糊涂了，二维时感觉特别清晰明朗。
• BBGG丶狮孒喵:我发现了一个问题，这题的初始化是不是有点问题？dp【0】 = 1，装满容量为0的背包，有1种⽅法，就是装0件物品。 但是如果第0个物品的重量刚好是0的话，dp【0】应该等于2才对，因为装满容量为0的背包，可以是装第0个物品，也可以不装第0个物品，即+0或者-0都等于0[哦呼][呆]