LeetCode 494：目标和问题解法精讲
LeetCode494
给你一个非负整数数组nums和一个整数target。
向数组中的每个整数前添加'+'或'-'，然后串联起所有整数，可以构造一个表达式：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。
示例 ：
输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
Python解法
回溯（会超时，仅供理解）
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: count = 0 def backtrack(nums: List[int], target: int, idx: int, Sum: int) -> int: nonlocal count if idx == len(nums): if Sum == target: count += 1 else: backtrack(nums, target, idx + 1, Sum - nums[idx]) backtrack(nums, target, idx + 1, Sum + nums[idx]) backtrack(nums, target, 0, 0) return count动态规划
from typing import List class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: total = sum(nums) # 无法凑出，直接返回0 if (total + target) % 2 != 0 or total < abs(target): return 0 aim = (total + target) // 2 # dp[i] = 凑出和为i的方案数 dp = [0] * (aim + 1) dp[0] = 1 # 和为0，空集1种方案 for num in nums: # 倒序遍历，避免重复选取数字 for i in range(aim, num - 1, -1): dp[i] += dp[i - num] return dp[aim]重要解释
1.aim = (total + target) // 2
设： 正数集合总和 = A 负数绝对值总和 = B
- 数组全部数字总和：(A + B = total)
- 最终表达式结果：(A - B = target)
两式相加：
A+B + A-B = total + target
2A = total + target
A = （total + target）// 2举例子验证
nums=[1,1,1,1,1], target=3 total=5
A=(5+3)/2=4
选 4 个数字加正号、1 个加负号：4-1=3，符合 target。
2.for循环代码
1. 公式含义
dp[i] = dp[i] + dp[i-num]
dp[i]：不选当前 num，凑和 i 的方案数dp[i-num]：选当前 num，凑和 i-num 的方案数2. 为什么必须倒序
一维数组复用同一个 dp，正序会重复拿同一个数字（完全背包），倒序保证每个数字只使用一次（01 背包）。
- 倒序从大到小遍历 i，更新
dp[i]时，dp[i-num]还是本轮数字未更新的旧值（上一轮状态），不会重复选当前 num。- 若从小到大正序，前面更新的
dp[i-num]会被后面 i 复用，同一个 num 多次累加。3. range 参数说明
range(aim, num - 1, -1)
- 起点：
aim（最大目标和）- 终点：
num-1，i 最小取num，i-num≥0，防止下标越界- 步长：
-1，从大到小倒序
Java解法
动态规划
class Solution { public int findTargetSumWays(int[] nums, int target) { int total = 0; for(int n : nums) total += n; if((total + target) % 2 != 0 || total < Math.abs(target)) return 0; int aim = (total + target) / 2; int[] dp = new int[aim + 1]; dp[0] = 1; for(int num : nums){ for(int i = aim; i >= num; i--){ dp[i] += dp[i - num]; } } return dp[aim]; } }C++解法
动态规划
#include <vector> using namespace std; class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int total = 0; for(int n : nums) total += n; if((total + target) % 2 != 0 || total < abs(target)) return 0; int aim = (total + target) / 2; vector<int> dp(aim + 1, 0); dp[0] = 1; for(int num : nums){ for(int i = aim; i >= num; i--){ dp[i] += dp[i - num]; } } return dp[aim]; } };