494. 目标和：回溯 dp双解法

背景

494. 目标和 - 力扣（LeetCode），首先想到回溯，因为每个数不是正就是负

回溯

然后写出了第一版代码，发现我的输出较预期结果多了8种情况？？？

咋就能多这么多呢？？？后来想了想是因为自己无脑套模板了，我这样写是不仅有 +当前数、-当前数，还允许不取当前数。把for去了就AC了（本题数组最大长度才20，如果像 416. 分割等和子集 - 力扣（LeetCode）最大数组长度200，肯定有的用例也超时了）

function findTargetSumWays(nums: number[], target: number): number {
    let res: number = 0

    function backTracing(nums: number[], startIndex: number, tempSum: number) {

        if (startIndex === nums.length) {
            if (tempSum === target) {
                res ++
            }
            
            return 
        }
                
        backTracing(nums, startIndex + 1, tempSum + nums[startIndex])
        backTracing(nums, startIndex + 1, tempSum - nums[startIndex])
        
    }

    backTracing(nums, 0, 0)

    return res
};

dp：此题用dp就需要多多思考了

回想下 1049. 最后一块石头的重量 II - 力扣（LeetCode），把石头分成两部分，然后抵消看最后剩的最小重量是多少。这就要求两部分的各自重量和相差的小，那让其中一部分近似总质量一半即可

现在这个问题也是把数组分成两部分（left 和 right），但是对最后抵消的结果要求是target

left + right = sum

left - right = target

则 left = (sum + target) / 2，问题变成了从当前数组中选取元素，使得元素和为 left 有多少种方法

dp[i][j]：在0-i件商品中挑选，有dp[i][j]种能占满j的方法

能感觉到还是dp，但是递推公式不再是0-1那样，因为dp含义已经改变了

遇到一个新的dp问题，先从二维开始思考吧，成功了再说一维的解法

递推公式

若当前容量 j 放不下第 i 个物品，那就不放，当前放满 j 容量的方法和只放 j-1 个物品时一样

当前容量 j 能放下第 i 个物品，如果不放，则有dp[i - 1][j]种方法。如果放，则有dp[i - 1][j - nums[i]] 种方法。所以放满 j 共有 dp[i - 1][j] + dp[i - 1][j - nums[i]]种方法

if (nums[i] > j) {
    dp[i][j] = dp[i - 1][j] 
} else {
    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
}

初始化：由递推公式知，需要初始化最左列和最上行

最上行就是当仅有一件物品0时，能放满j有几种方法。找到刚好和物品0大小的j，将dp[0][j]赋值为1即可

最左列就是当前从0-i中选择，能放满0有多少种方法

let zeroNums: number = 0
for (let i = 0; i < nums.length; i ++) {
    if (nums[i] === 0) {
        zeroNums ++
    }

    dp[i][0] = Math.pow(2, zeroNums)
}