leetcode(力扣) 1494. 目标和 (动态规划 & 01背包问题)

文章目录

• ​​题目描述​​
• ​​思路分析​​
• ​​完整代码​​

题目描述

给你一个整数数组 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

思路分析

在做这道题之前一定要先看 ​​01背包理论基础​​

这道题转换成01背包问题的思路和上一题 ​​1049. 最后一块石头的重量 II​​ 差不多。

题目中给出的数组值可以选择给‘+’号或者‘-’号，那么此时阵营就出来了，赋加号的为加号阵营，剩下的是减号阵营。

设题目所给数组nums 的和为sum，目标值为target，A阵营为加号阵营，其和为sumA，B阵营为减号阵营，其和为sumB。

则有

• target = sumA - sumB。

• sum = sumA + sumB

  上述两式相加则有 target + sum = 2 * sumA

sumA = (target+sum) / / 2

因为2 * sumA必为偶数，所以target + sum 必为偶数。

还有一个就是 如果所有值都赋加号也没target大，即 target > sum也是不行的。

那么sumA就是我们要求的背包。

老规矩，五部曲开始：

1.确定dp数组含义：

dp[j] 表示 背包容量为j时 有dp[j]种组合方法。

2.确定状态转移公式：

这块是这道题的难点。

要一直重复告诉自己 dp[j]表示的是背包容量为j时有多少种组合方法。

这里我用一维数组来分析，脑子里要有二维和一维的区别。

在计算新的dp[j]的时候，肯定要继承上一个dp[j]的状态，这里我说一个例子吧，假如本轮状态要考虑加入2这个数，上一轮状态没有考虑2，此处要明白上一轮虽然没有考虑2，但是已经装满背包j了，上一轮的状态dp[j]已经是要记录的答案了，只是没有考虑2，所以本轮计算新的dp[j]的时候要算上上一轮的答案，然后再计算本轮考虑了2的结果这个自然就是dp[j-2]，这点不懂的话可以看01背包理论基础。

所以状态转移公式：dp[j] = dp[j] + dp[j - num]。

当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数

3.初始化dp：

完整代码

dp = [0] * 10001
    dp[0] = 1
    temp = (sum(nums) + target)//2 # 背包容量
    if target > sum(nums) or (sum(nums)+target)%2==1:
        return 0
    for i in range(len(nums)):
        for j in range(temp,nums[i]-1,-1):
            dp[j] += dp[j-nums[i]]
    return dp[temp]