这道题主要是利用动态规划进行求解,优化的时候可以找规律,转化成正常的背包问题。
原题
给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
<code>
输入:
nums:
[1,
1
,
1
,
1
,
1
],
S:
3
输出:
5
解释:
-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
一共有5种方法让最终目标和为3。
/<code>注意:
数组非空,且长度不会超过20。初始的数组的和不会超过1000。保证返回的最终结果能被32位整数存下。原题url:
https://leetcode-cn.com/problems/target-sum/
解题
简单递归
最简单的方法就是计算出所有的可能性,如果最终结果等于目标值,则说明该情况可以。直接看一下代码:
<code>
public
class
Solution
{int
result =0
;public
int
findTargetSumWays
(
int
[] nums,int
S) { findTargetSumWays(nums, S,0
,0
);return
result; }public
void
findTargetSumWays
(
int
[] nums,int
S,int
index,int
sum) {if
(index == nums.length) {if
(sum == S) { result++; }return
; } findTargetSumWays(nums, S, index +1
, sum + nums[index]); findTargetSumWays(nums, S, index +1
, sum - nums[index]); } }/<code>方法很简单,但是时间复杂度太高,O(2^n),执行用时在 java 中也只打败了31.65%,看来确实不够好。
简单的动态规划
这其实类似于背包问题,有容量要求(部分数字之和等于目标值)。首先我们来想一下状态转移方程:
我们用二维数组dp[i][j]表示用数组中的前i个元素,组成和为j的方案数。考虑第i个数nums[i],它可以被添加 + 或 -,因此状态转移方程如下:
<code>dp[
i
][j
] = dp[i - 1
][j - nums[i
]] + dp[i - 1
j + nums[i
]]/<code>也可以写成递推的形式:
<code>dp[
i
][j + nums[i
]] += dp[i - 1
][j
] dp[i
][j - nums[i
]] += dp[i - 1
][j
]/<code>因为题目中提到所有数的和不超过 1000,那么 j 的最小值可以达到 -1000。在 java 中,是不允许数组的下标为负数的,因此我们需要给dp[i][j]的第二维预先增加 1000,那么新的递推关系如下:
<code>dp[
i
][j + nums[i
] + 1000] += dp[i - 1
][j + 1000
] dp[i
][j - nums[i
] + 1000] += dp[i - 1
][j + 1000
]/<code>接下来我们看看代码:
<code>
public
class
Solution
{public
int findTargetSumWays(int[] nums, intS
) {if
(S
>1000
||S
< -1000
) {return
0
; } intmax
=1000
; int[][] dp = new int[nums.length][max
*2
+1
]; dp[0
][nums[0
] +max
] =1
; dp[0
][-nums[0
] +max
] +=1
;for
(int i =1
; i < nums.length; i++) {for
(int sum = -max
; sum <=max
; sum++) {if
(dp[i -1
][sum +max
] >0
) { dp[i][nums[i] + sum +max
] += dp[i -1
][sum +max
]; dp[i][-nums[i] + sum +max
] += dp[i -1
][sum +max
]; } } }return
dp[nums.length -1
][S
+max
]; } }/<code>提交OK,时间复杂度为O(N ∗ max),max 代表数组中所有数字之和的最大值,执行用时在 java 中打败了58.91%,看来还有很大的提升空间。
动态规划 + 找规律
我们想一下,之所以上面的方法会涉及到 max,因为所谓的求和,并不只是加法,也可以用减法。这和我们一般理解的背包问题还是有所不同的,那么我们是否可以将本题转换成真正意义上的背包问题呢?
首先,我们可以将这组数看成两部分,P 和 N,其中 P 使用正号,N 使用负号,那么可以推导出一下关系:
<code>
1
、target
=
sum(P)
-
sum(N)
2
、sum(nums)
=
sum(P)
+
sum(N)
由1可以得出:sum(P)
=
target
+
sum(N)
由2可以得出:sum(N)
=
sum(nums)
-
sum(P)
综合以上,可以得出:
sum(P)
=
(target
+
sum(nums))
/
2
/<code>因此只要找到一个子集,令它们都取正号,并且和等于 (target + sum(nums))/2,就证明存在解,这就属于正常的0-1背包问题的范畴了。需要注意target + sum(nums)必须为偶数,否则 sum(P) 就是小数了,这和题目要求的所有数都是非负整数不符。
接下来我们看看代码:
<code>
public
class
Solution
{public
int
findTargetSumWays
(
int
[] nums,int
S) {if
(S >1000
|| S-1000
) {return
0
; }int
sumNums =0
;for
(int
num : nums) { sumNums += num; }int
newTarget = sumNums + S;if
((newTarget &1
) ==1
) {return
0
; } newTarget = newTarget /2
;int
new
int
[newTarget +1
]; dp[0
] =1
;for
(int
num : nums) {for
(int
sum = newTarget; sum >= num; sum--) { dp[sum] += dp[sum - num]; } }return
dp[newTarget]; } }/<code>提交OK,时间复杂度是O(n * newTarget),其中, newTarget = (target + sum(nums))/2,和前面方法中的max相比,sum(nums) <= max,如果target > max,也会直接返回0,因此这个方法的时间复杂度更优。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是利用动态规划,优化时可以找规律,转化成正常的背包问题。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
https://death00.github.io/