LeetCode-494-Target Sum

这个题也是一道动态规划题目。题意是:给出一系列数和一个目标数,使用+-来使这些数字的和等于给定的目标数,求总共可行的方法数。

例子:输入[1, 1, 1, 1, 1]target = 3,那么:

所以最后的输出结果是:5

思路:
这个题比较类似于之前做过的求二叉树上和为指定数值的路径。我们可以写一个辅助函数

这个函数计算:以 nums 的位于 left 和 right 之间的元素为输入,使用+-使得这些数字之和等于 target 的方法数。声明一个 int 型变量 res,初始时 res = 0,表示总的方法数。对于当前区间[i,j)来说,如果我们对第一个数 nums[i]使用+,那么剩余的目标数为 target - nums[i],如果我们对第一个数 nums[i]使用-,那么剩余的目标数为 target+nums[i],所以有:

如果left > right, 此时如果 target = 0的话,那么这种方法就可以使得和为 target,返回1,否则就返回0。

根据以上分析,不难写出如下的代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据