每天一道DP防止抑郁
題目描述：
給定一個非負(fù)整數(shù)數(shù)組炉旷，a1, a2, ..., an, 和一個目標(biāo)數(shù)码邻，S。現(xiàn)在你有兩個符號 + 和 -镶奉。對于數(shù)組中的任意一個整數(shù)，你都可以從 + 或 -中選擇一個符號添加在前面溪王。
返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號的方法數(shù)腮鞍。
示例 1:
輸入: 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種方法讓最終目標(biāo)和為3。
首先莹菱，我們來推導(dǎo)幾個公式移国。
設(shè)nums數(shù)組中添加負(fù)號的數(shù)的和為SumN，nums數(shù)組中添加正號的數(shù)的和為SumP道伟，數(shù)組的和為Sum迹缀。
由題意，我們可以得出：
SumP - SumN = S ==> SumP + SumP = S + SumN + SumP ==> 2 * SumP = S + Sum ==> SumP = (Sum + S) / 2蜜徽。
所以這道題轉(zhuǎn)化為從nums數(shù)組中選擇數(shù)字求和祝懂，要求這個和等于Sum加上S除以二。求有總共有多少種情況拘鞋。
這個問題進(jìn)而轉(zhuǎn)化為子集合問題砚蓬，所以可以用0-1背包問題來解決這道題目。
狀態(tài)轉(zhuǎn)移方程為：dp[i] = dp[i] + dp[i - nums[i]] (dp[i] : 從nums中取數(shù)盆色，使得這些數(shù)字的和為i的取法)
代碼如下：
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int i : nums) {
sum += i;
}
/*
剪枝灰蛙。如果全部選正號的和都小于S的話，怎么組合都達(dá)不到S
*/
if (sum < S || (S + sum) % 2 == 1) {
return 0;
}
int target = (S + sum) / 2;
int[] dp = new int[target + 1];//dp[i]: 從nums中取數(shù)隔躲，使得這些數(shù)字的和為i的取法
dp[0] = 1;
for (int num : nums) {
for (int i = target; i >= num; i--) {
dp[i] += dp[i - num];
}
}
return dp[target];
}
}
