网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第32天，活动详情查看：2022首次更文挑战」
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入： 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 复制代码
示例 2：
输入： nums = [1], target = 1 输出： 1 复制代码
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
解题思路
这个问题乍一看可能感觉有些复杂，每1个数字都有正负2种可能，2个数字就是4种可能，3个数字就是8种可能，而本题又要求运算结果等于 target 的不同表达式数目,emmmm....
其实我们可以换个角度看这个问题，当只有一个数字的时候，我们很确定的可以得到两个表达式的结果，x 和 -x，然后，又因为下一个数字无非也就是两种可能，正或者负，所以我们一个一个数字的推导过去，就可以得到前面的数字组合的所有可能的结果，最后获取所有数字都使用可以获取结果值为 target 的表达式的数目即可。这明显是一个推导的问题，所以我们可以用动态规划来做。
状态定义：根据上述的分析结果可以知道，这里面有两个变量，使用数字的数量和可以求得的结果值，所以我们定义二维 dp dp[i][j] 表示前 i 个数字可以求得 j 的表达式的数目。
转移方程：因为每一个数字只有两种可能，为正或负，所以 dp[i][j] 可以由前 i-1 个数字组合 j-x 得到，也可以由前 i-1 个数字组合 j+x 得到，x 是第 i 个数字的值，所以得到 dp[i][j] = dp[i-1][j-x]+dp[i-1][j+x]。
有了状态定义和转移方程，接下来就去实现代码吧！💪
代码实现
var findTargetSumWays = function (nums, target) { // 获取输入数组的长度 const len = nums.length, // 初始化 dp 数组 dp = Array(len + 1) // 获取输入数组所有整数的和值 let total = 0 for (let i = 0; i < len; i++) total += nums[i] // 因为数字下标没有负数，但是表达式的结果可能为负数，所以拿到和值，基于和值做一个结果的偏移 for (let i = 0; i <= len; i++) dp[i] = Array(total * 2).fill(0) // 初始化 dp[0][0] = 1 dp[0][total] = 1 // 初始化前 i 个数字的和值 let sum = 0 // 遍历 i，求每一层 dp for (let i = 1; i <= len; i++) { // 获取当前数字的值 const x = nums[i - 1] // 获取前 i 个数字的和值 sum += x for (let j = -sum; j <= sum; j++) { // 求解范围内的每个 dp // 这里要注意j-x和j+x可能超出了我们数组的下标，所以运算的时候要 || 0 dp[i][j + total] = (dp[i - 1][j - x + total] || 0) + (dp[i - 1][j + x + total] || 0) } } // 返回所有数字都使用，求得 target 的表达式的数目 // 同理，因为 target+total可能超出dp数组的下标，要拿 0 兜底 return dp[len][target + total] || 0 } 复制代码
至此我们就完成了 leetcode-494-目标和
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
