问题描述

  1. 给定一个非负数数组和一个目标和，对于数组中的任意一个元素，都可以选择在前面添加+或-，返回所有使数组和为目标和的所有符号添加方法数;目标和不会超过1000.
  2. https://leetcode-cn.com/problems/target-sum/

问题关键

  1. 这个问题最大的难点就在于if-else逻辑，很容易弄错！！
  2. 回溯/递归/枚举法：需要注意一点，只有当 i < length 时，才有必要向后走；只有 i==length 时，才有必要判断sum==S；
  3. 动态规划
    • dp[i][j] = dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]] ：这种状态转移方程的优点在于便于理解，缺点在于需要考虑边界情况，而且在判断if-else逻辑时，容易弄错！！
    • dp[i][j+nums[i]] += dp[i-1][j], dp[i][j-nums[i]] += dp[i-1][j] 这种递归表达式的缺点在于不容易理解，优点在于他是正序的从dp[i-1][j]向其他两种情况推，再加上数组元素和不大于1000的条件限制，只需要对dp[i-1][j]做判断是否存在就可以，不需要考虑dp[i][j+nums[i]]和dp[i][j-nums[i]]边界是否存在的情况，而且还可以加快计算速度。