动态规划：目标和！ 题目描述

给你一个整数数组 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=0def 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=3if(sum(nums)+target==1): print(0)t= (sum(nums)+target)//2t=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为负的时候,要给他绝对值,因为 挑30个负的,就等于时挑三十个负的

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

 最终效果为

 总结

j容量的最大种数dp[j] 为 上一个状态即dp[j-num[i]]得来.