解题思路:1.因为每个数字都有正负两种选择,所以可以采用回溯算法。(会超时)
2.分成两个集合,分别为正数集合(left)和负数(right)集合。
left + right = Sum ---> right = Sum - left
left - right = target
联立得到:
left = (target + Sum) / 2
如果不能整除,则凑不出target
dp数组含义:装满容量为j的背包的方法
递推公式:d[j] = d[j] + d[j-numbers[i]](放i和不放i)
初始化:dp[0] = 1(装满容量为0的背包有1种方法),其余非0下标初始化为0
代码实现:文章来源:https://www.toymoban.com/news/detail-834823.html
文章来源地址https://www.toymoban.com/news/detail-834823.html
到了这里,关于leetcode:494.目标和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!