[!info] related notes 动态规划 背包 DP

目标和

题目链接：https://leetcode.cn/problems/target-sum/

关键转化

设加号集合和为 P，减号集合和为 N。

则：

P - N = target
P + N = sum

两式相加得：

P = (sum + target) / 2

问题转成：

从数组中选一些数，使它们的和恰好等于 P，有多少种选法？

这是 01 背包方案数。

状态

dp[j] 表示凑出和 j 的方案数。

转移

dp[j] += dp[j - num]

JavaScript

var findTargetSumWays = function(nums, target) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum + target < 0 || (sum + target) % 2 !== 0) return 0;

    const bag = (sum + target) / 2;
    const dp = new Array(bag + 1).fill(0);
    dp[0] = 1;

    for (const num of nums) {
        for (let j = bag; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }

    return dp[bag];
};