一套常见的背包问题的应用

https://leetcode-cn.com/problems/target-sum/solution/yi-tao-kuang-jia-jie-jue-bei-bao-wen-ti-58wvk/

一、目标和
0-1背包的一种变形，原来适用于求最大值，这道题用于求组合数

/* 
    0-1背包变形
    target = x - y;
    sum = x + y;
    x = (sum + target) / 2;
    用nums中元素组成x，有多少种方法
 */
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int n = nums.length;
        for (int i : nums) {
            sum += i;
        }

        if (sum < target || (sum + target) % 2 == 1) {
            return 0;
        }

        int s = (sum + target) / 2;
        int dp[] = new int[s + 1];
        dp[0] = 1;

        for (int i = 0; i < n; ++i) {
            for (int j = s; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[s];
    }
}