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]
}