动态规划：目标和！

题目描述

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

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

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

来源：力扣（LeetCode）

?

题目地址

示例 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

分析

数组可以分成两个部分一个是我们求的那一部分(用left表示),另一部分(用right表示)是与之相减的那一部分,可以得到left+rgylin=sum, left-right= target相加

=>继而得到 left=(target+right)//2

?利用回溯算法

'''可以将nums分成两部分left 和right
其中 left+right=sum
    left-right=target
    带入得到
    left = (sum+target)//2
    sum和target是固定的
    所以就转化成找一个left 数组使得 求和为(sum+target)//2
    那么就变成了求组合问题
'''

#用回溯
path=[]
result=[]
count=0
def backTo(s, t, startIndex,sum_t):
    global count
#查看是否满足条件
    if(sum_t>t):
        return
    if(sum_t==t):
        count+=1
        return
    for i in range(startIndex,len(s)):
        sum_t+=s[i]
        path.append(s[i])
        backTo(s,t,i+1,sum_t)
        #回溯
        path.pop()
        sum_t -= s[i]


nums =  [1,1,1,1]
target=3
if(sum(nums)+target==1):
    print(0)
t= (sum(nums)+target)//2

t=abs(t)
backTo(nums,t,0,0)
return result

?利用动态规划

首先确定dp具体表示的是:dp[j]? 容量为j时所有几种方法来满足target
推导dp : 举个例子=>d[5] ，num[i] =2 等于什么呢? d[5] 可以由容量为3 也就是dp[3] 再加上容量为2 即:dp[3+2] 求得?
所以dp[j]= dp[j-num[i]]
初始化:dp[0] 容量为0时即装满容量0 的背包,即0个物品所以由1种

编写代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        if(sum(nums)<target):
            return 0
        if((sum(nums)+target)%2==1):
            return 0
        t= (sum(nums)+target)//2
        t=abs(t)
        dp= [0]*(t+1)
        
        dp[0]=1
        print(dp)
        for i in range(len(nums)):
            for j in range(t,nums[i]-1,-1):
                dp[j] += dp[j-nums[i]]
            
        return dp[-1]

这里注意一点就是: 当target为负的时候,要给他绝对值,因为挑30个负的,就等于时挑三十个负的

如果不加的话,会报错比如