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 3Python解法回溯会超时仅供理解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)两式相加AB A-B total target2A total targetA total target// 2举例子验证nums[1,1,1,1,1], target3 total5A(53)/24选 4 个数字加正号、1 个加负号4-13符合 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-1i 最小取numi-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(vectorint 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; vectorint 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]; } };