這道題主要是利用動態規劃進行求解，優化的時候可以找規律，轉化成正常的揹包問題。
原題
給定一個非負整數數組，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
[] dp =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/
