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

1. 数组全部数字总和：(A + B = total)
2. 最终表达式结果：(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]; } };