1. 题目

2. 思路

(1) 动态规划

• 这道题可以转化为0/1背包问题，由于总和sum和目标和target已经确定，因此，要求的即是从数组中挑出和为(sum-target)/2的方案数。
• 首先确定动态规划数组的含义，dp[i][j]表示从下标为[0,i)的元素中挑出和为j的方案数，初始化时令dp[0][0]=1即可。
• 若nums[i-1]>j，则必然不取nums[i-1]，因此，dp[i][j]=dp[i-1][j]；否则，dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]]，即从下标为[0,i-1)的元素中挑出和为j和j-nums[i-1]的方案数之和。

(2) 动态规划优化

• 状态压缩后，dp[i]表示从数组中挑出和为i的方案数。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}if (sum < target) {return 0;}int differ = sum - target;if ((differ & 1) == 1) {return 0;}target = differ >> 1;int n = nums.length;int[][] dp = new int[n + 1][target + 1];dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= target; j++) {if (nums[i - 1] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];}}}return dp[n][target];}
}class Solution1 {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}if (sum < target) {return 0;}int differ = sum - target;if ((differ & 1) == 1) {return 0;}target = differ >> 1;int n = nums.length;int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i < n; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[target];}
}