Comment on page
Target Sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols
+and-. For each integer, you should choose one from+and-as its new symbol.Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
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 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- 1.The length of the given array is positive and will not exceed 20.
- 2.The sum of elements in the given array will not exceed 1000.
- 3.Your output answer is guaranteed to be fitted in a 32-bit integer.
DP - backpack 转化为背包问题后用DP求解
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if(S > sum || (sum + S) % 2 == 1) return 0;
return subsetSum(nums, (sum + S) / 2);
}
private int subsetSum(int[] nums, int S){
int[] dp = new int[S + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = S; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[S];
}
}
The difference is that if you update
dpwhile:- increasing
ithen the previous partial resultdp[i - coin]is the result that has consideredcoinalready - decreasing
ithen the previous partial resultdp[i - coin]is the result that has not consideredcoinyet
/**
* @return number of ways to make sum s using repeated coins
*/
public static int coinrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = coin; i <= s; i++)
dp[i] += dp[i - coin];
return dp[s];
}
/**
* @return number of ways to make sum s using non-repeated coins
*/
public static int coinnonrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = s; i >= coin; i--)
dp[i] += dp[i - coin];
return dp[s];
}
Last modified 3yr ago