【动态规划】力扣494.目标和：一文学会「转化思想」与「01背包应用」

问题重述

给定非负整数数组nums和目标值target，在每个数字前添加+或-，使表达式结果等于target，求不同表达式的数量。

题目链接：494. 目标和 - 力扣（LeetCode）

潜在关系

设：

• left：所有添加+的数字之和（正数集合）

• right：所有添加-的数字之和（负数集合的绝对值）

• 数组总和为sum

根据题意：

left+right=sum

left-right=target

得到：

left= (sum + target) //2

问题转化

从 nums 中选出若干个数，使它们的和恰好等于 pos，求有多少种选法

约束条件：

1. (sum + target)必须为偶数（因为 pos 必须是整数）

2. left 必须 ≥ 0（不能选负数个数字）

3. 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：

1. 不选当前数字：方法数 = 原来的dp[j]

   • 保持之前已经有的方法数

2. 选当前数字：方法数 =dp[j - nums[i]]

   • 前提：j ≥ nums[i]（背包容量要装得下这个数字）

   • 含义：如果选了当前数字（重量为nums[i]），那么剩下的容量j - nums[i]需要被装满

   • dp[j - nums[i]]就是装满剩下容量的方法数

3. 总方法数= 不选的方法数 + 选的方法数

   • 这就是组合计数的加法原理

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]

易错点总结

1. 边界条件：

   • sum < abs(target)时直接返回0

   • (sum + target)必须是偶数

   • left不能为负数

2. DP数组初始化错误：

   • dp[0]必须初始化为1

   • 其他位置初始化为0

3. 遍历顺序错误：

   • 必须从后往前遍历背包容量

   • 否则会重复计算

4. 不理解状态转移方程：

   • 记住：dp[j] = 不选的方法 + 选的方法

   • 选的方法数 = 装满剩余容量的方法数