【动态规划】力扣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]