【动态规划】力扣494.目标和：一文学会「转化思想」与「01背包应用」
问题重述
给定非负整数数组nums和目标值target，在每个数字前添加+或-，使表达式结果等于target，求不同表达式的数量。
题目链接：494. 目标和 - 力扣（LeetCode）
潜在关系
设：
left：所有添加
+的数字之和（正数集合）right：所有添加
-的数字之和（负数集合的绝对值）数组总和为
sum
根据题意：
left+right=sum
left-right=target
得到：
left= (sum + target) //2
问题转化
从 nums 中选出若干个数，使它们的和恰好等于 pos，求有多少种选法
约束条件：
(sum + target)必须为偶数（因为 pos 必须是整数）left 必须 ≥ 0（不能选负数个数字）
sum ≥ abs(target)（否则不可能达到目标）
动态规划解法详解
1. 转化为01背包问题
背包容量：left
= (sum + target) / 2物品：数组中的每个数字（重量 = 数值）
价值：这里不是求最大价值，而是求方法数（计数型背包）
问题：装满背包有多少种方法？
2. DP数组定义
dp[j]表示：装满容量为 j 的背包，有 dp[j] 种方法
3. 初始化
dp[0] = 1
装满容量0的背包有一种方法：什么都不选（空集）
4. 状态转移方程
dp[j] = dp[j] + dp[j - nums[i]]公式拆解理解：
对于当前数字nums[i]，要装满容量j：
不选当前数字：方法数 = 原来的
dp[j]保持之前已经有的方法数
选当前数字：方法数 =
dp[j - nums[i]]前提：
j ≥ nums[i]（背包容量要装得下这个数字）含义：如果选了当前数字（重量为
nums[i]），那么剩下的容量j - nums[i]需要被装满dp[j - nums[i]]就是装满剩下容量的方法数
总方法数= 不选的方法数 + 选的方法数
这就是组合计数的加法原理
5. 遍历顺序
必须从后往前遍历背包容量：
python
for j in range(left, nums[i] - 1, -1): # 从大到小 dp[j] += dp[j - nums[i]]
为什么不能从前往后？
假设nums = [1, 1], left= 2：
如果从前往后：
处理第一个1：
dp[1] = 1,dp[2] = 1处理第二个1时，
dp[2] = dp[2] + dp[1] = 1 + 1 = 2这相当于
[1, 1]被用了两次（重复计算）
从后往前：
保证计算
dp[j]时，dp[j - nums[i]]是上一轮的状态避免同一物品被多次使用
完整代码实现
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: summ=sum(nums) if (summ+target)%2==1 or summ<abs(target): return 0 #不能整除，说明有小数 left=(summ+target)//2 dp=[0]*(left+1) #dp[j]:装满容量为j的背包有dp[j]种方法 if left<0: return 0 dp[0]=1 for i in range(len(nums)): for j in range(left,nums[i]-1,-1): dp[j]=dp[j]+dp[j-nums[i]] # dp[j]:不选当前数字，保持原来方法数 # dp[j-nums[i]]:选当前数字，那么当前方法取决于j-nums[i]的方法数 return dp[left]易错点总结
边界条件：
sum < abs(target)时直接返回0(sum + target)必须是偶数left不能为负数
DP数组初始化错误：
dp[0]必须初始化为1其他位置初始化为0
遍历顺序错误：
必须从后往前遍历背包容量
否则会重复计算
不理解状态转移方程：
记住：
dp[j] = 不选的方法 + 选的方法选的方法数 = 装满剩余容量的方法数