Cocolib

Appearance

On this page

目标和 ​

TIP

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

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

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

image-20230624102634544

思路 ​

动规五部曲 ​

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

如何将问题转化为0-1背包问题，这道题和前面两道题略有不同，前两道是让我们求背包的容量（能否装满/容量之内的最大值），但是这道是让我们求装满背包有多少种方法。

  • 首先观察发现，如果sum-target是一个奇数，我们发现不能满足相减之后得到target
  • dp数组以及下标的含义：填满j（包括j）这么大容积的包，有dp[j]种方法
js
var findTargetSumWays = function(nums, target) {
    let sum = nums.reduce((pre,cur)=>pre+cur,0)
    if((sum-target)%2!=0 || sum-target<0)    return 0
    let n = Math.floor((sum-target)/2) //背包容量
    let dp =[]
    for(let j=0;j<=n;j++){
        dp[j] = 0
    }
    dp[0] = 1		//初始化为 1
   for(let i=0;i<nums.length;i++){     //物品
        for(let j=n;j>=nums[i];j--){           //背包
            dp[j] += dp[j-nums[i]]
        }
    }
    console.log(dp)
    return dp[n]
};