卡码讲的一般，没太整明白： https://programmercarl.com/背包理论基础01背包-1.html#算法公开课

还是推荐灵神： 灵神的课

94. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-'
，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于
target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为
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 +1 + 1 + 1 + 1 - 1 = 3 示例 2：

输入：nums = [1], target = 1 输出：1

提示：

1 <= nums.length <= 20 0 <= nums[i] <= 1000 0 <= sum(nums[i]) <= 1000 -1000 <=
target <= 1000

使用dfs的做法：（记忆化搜索）

function findTargetSumWays(nums: number[], target: number): number {
    // sum 所有值的总和； p  所有正数的和
    // sum - p 所有负数的和
    // 目标和为正数和减去负数和 t = p - (sum - p)
    // 所以正数和 p = ( t + sum ) / 2
    // 问题转化为，从nums中选一些数，使得他们的和恰好为( t + sum ) / 2的个数
    if (nums.length === 0) {
        return target === 0 ? 1 : 0;
    }
    const sum = nums.reduce((a, b) => a + b, 0);

    const p = (target + sum) >> 1; // 右移一位等同于除以2并向下取整
    const len = nums.length;
    const memo = new Map<string, number>();

    // 01背包
    const dfs = (i: number, capacity: number): number => {
        if (i < 0) {
            return capacity === 0 ? 1 : 0;
        }
        const key = `${i}-${capacity}`;
        if (memo.has(key)) {
            return memo.get(key) ?? 0;
        }
        let result = 0;
        // 取或者不取
        if (capacity < nums[i]) { // 容量不够，不取
            result = dfs(i - 1, capacity);
        }
        result = dfs(i - 1, capacity) + dfs(i - 1, capacity - nums[i]); // 不取和取的方案数加起来
        memo.set(key, result);

        return result;
    };

    // 判断边界，p不能为奇数以及负数
    if (p * 2 !== target + sum || p < 0) {
        return 0;
    }

    return dfs(len - 1, p);
}

递归的做法：

function findTargetSumWays(nums: number[], target: number): number {
    if (nums.length === 0) {
        return target === 0 ? 1 : 0;
    }
    const sum = nums.reduce((a, b) => a + b, 0);

    const p = (target + sum) >> 1; // 右移一位等同于除以2并向下取整
    let dp: number[][] = Array.from(
        { length: nums.length + 1 },
        () => new Array(p + 1).fill(0),
    );
    dp[0][0] = 1;
    // 从递归1:1翻译过来的递推，外层是每个数据，内层是每个target;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < p + 1; j++) {
            if (j < nums[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = dp[i][j] + dp[i][j - nums[i]];
            }
        }
    }
    return dp[nums.length][p];
}