Re: [閒聊] 每日leetcode
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]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.171 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735310652.A.FD3.html
討論串 (同標題文章)
完整討論串 (本文為第 1224 之 1554 篇)：