前端刷题路-Day58：目标和（题号494）

这是我参与更文挑战的第22天，活动详情查看： 更文挑战

目标和（题号494）

题目

给你一个整数数组 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 <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 100

链接

leetcode-cn.com/problems/ta…

解释

这题啊，这题是经典动态规划。

首先看看暴力解法，暴力解法就很简单了，直接一个递归找到所有可能性就完事了，这没啥可说的。

重点是动态规划的思路，笔者是在回家的路上思考的，思考了一路也没有什么好的想法，即使这题就差把动态规划四个字写在题目上了。

看来答案才知道原来这题是得通过一些计算才能动态规划的，笔者的DP一直卡在符号上面，有了符号就不太方便DP了，因为公式一直想不出来。

那要怎样才能把符号去掉呢？这就需要一些计算了。

这里直接引用官方的解释了，笔者也就不二次翻译了?：

记数组的元素和为sum，添加 – 号的元素之和为 neg，则其余添加 + 的元素之和为 sum−neg，得到的表达式的结果为

$$(sum−neg)−neg=sum−2⋅neg=target$$

© 版权声明

文章版权归作者所有，未经允许请勿转载。

THE END

前端