494. Target Sum
思路
看是要用backtracking还是用dp也可以
dp:
建立两个map:map1、map2
map的key会是目前得到过的数字
value是得到过key的次数
map[i]=j
表示目前的到过j次i
首先设map1[0]=1
接着每次都去遍历map1，并且令
map2[key-nums[i]]+=j　、　map2[key+nums[i]]+=j
最后回传map1[target]就好
golang code :
func findTargetSumWays(nums []int, target int) int {
dp1 := make(map[int]int)
dp2 := make(map[int]int)
dp1[0] = 1
for i := 0; i < len(nums); i++ {
for key, val := range dp1 {
dp2[key-nums[i]] += val
dp2[key+nums[i]] += val
}
dp1 = dp2
dp2 = make(map[int]int)
}
return dp1[target]
}