494 目标和（动态规划）

妖狐艹你老母 2023-01-24 02:12 162阅读 0赞

**1. 问题描述：**

给你一个整数数组 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  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/target-sum

**2. 思路分析：**

分析题目可以知道这是一道组合的问题，我们需要知道所有的组合方案才可以求解出最终的方案数目，所以最简单的解决思路是暴力枚举，也即枚举所有可能的组合方案，因为需要尝试所有可能的组合方案所以我们尝试**动态规划**递推的思路解决，动态规划有两个主要的步骤：① 状态表示 ② 状态计算， 由题目可知，我们需要求解的是目标和为target的组合数目，所以涉及到一个属性为目标和s，对于当前目标和为j的情况下，当前的nums\[i\]有两种选择，一种是取正数，另一种是取负数，所以对应着两个状态的转移，也即前一个目标和为j - nums\[i\]和j + nums\[i\]的组合数目。综上我们可以定义dp为二维数组或者列表，定义dp\[i\]\[j\]为前i个数目标和为j的组合数目，使用两层循环进行状态计算，第一层循环表示当前是第i个数，第二层循环表示目标和为j（也即枚举可能存在的状态），这里需要注意边界的问题，因为目标和j有可能是负数，也即第二维的状态有可能是负数所以我们需要在数组或者列表对应的目标和上加上一个偏移量offset，这里可以设置offset = 1000。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def findTargetSumWays(self, nums: List[int], S: int) -> int:
            # 先判断一下当前的target是否满足条件, 因为目标和最大是1000, 所以最小是-1000
            if S < -1000 or S > 1000: return 0
            n = len(nums)
            # 因为数组是不允许负数的所以需要加上一个偏移量
            offset = 1000
            dp = [[0] * 2001 for i in range(n + 1)]
            # 边界
            dp[0][offset] = 1
            for i in range(1, n + 1):
                # 枚举可能的目标和
                for j in range(-1000, 1001):
                    if j - nums[i - 1] >= -1000:
                        # 当前nums[i]取正数的情况
                        dp[i][j + offset] += dp[i - 1][j - nums[i - 1] + offset]
                    # # 当前nums[i]取负数的情况
                    if j + nums[i - 1] <= 1000:
                        dp[i][j + offset] += dp[i - 1][j + nums[i - 1] + offset]
            return dp[n][S + offset]