改變一組數(shù)的正負(fù)號使得它們的和為一給定數(shù)

494. Target Sum (Medium)

Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation:-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 = 3There are 5 ways to assign symbols to make the sum of nums be target 3.

題目描述：

??給定一個全為1的數(shù)組，和一個目標(biāo)值，數(shù)組中每個元素可正可負(fù)，求出可以有多少種組合使得數(shù)組的和為目標(biāo)值。

思路分析：

??我們將添加“+”的數(shù)放入集合P，其它的數(shù)放入集合N，于是我們有：

sum(P) - sum(N) = target sum(P) + sum(N) = sum

??于是有sum(P) = (target + sum) / 2，那么不妨這樣理解題意，從一個數(shù)組中選定一些數(shù)，使它們的和為sum(P)，如此就變成了很經(jīng)典的0/1背包問題，從一個n大小的背包中選出總和為sum(P)的方案個數(shù)。

??狀態(tài)表示：dp[i] [j]代表前i個數(shù)中和為j的方案個數(shù)。
??狀態(tài)轉(zhuǎn)移方程：dp [i] [j] = dp[i-1] [j] + dp[i-1] [j-nums[i]]，dp [0] [0] = 1
??返回結(jié)果：dp[n] [target],n為數(shù)組大小，target為sum(P)。

代碼：

public int findTargetSumWays(int []nums,int S){int sum=0;for(int num:nums){sum=sum+num;}int target=(sum+S)/2;int []dp=new int[target+1];dp[0]=1;for(int num:nums){for(int i=target;i>=num;i--){dp[i]=dp[i]+dp[i-num];}}return dp[target]; }

DFS解法

public int findTargetSumWays(int[]nums,int S){return findTargetSumWays(int[]nums,int S); } private int findTargetSumWays(int []nums,int start int S){if(start==nums.length){return S==0?1:0;}return findTargetSumWays(nums,start+1,S-nums[start])+findTargetSumWays(nums,start+1,S+nums[start]); }

轉(zhuǎn)載于:https://www.cnblogs.com/yjxyy/p/11119414.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的动态规划（0-1背包）--- 改变一组数的正负号使得它们的和为一给定数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。