class Solution(object):
def findTargetSumWays(self, nums, S):
if not nums:
return 0
dic = {nums[0]: 1, nums[0]: 1} if nums[0] != 0 else {0: 2}
for i in range(1, len(nums)):
tdic = {}
for d in dic:
tdic[d + nums[i]] = tdic.get(d + nums[i], 0) + dic.get(d, 0)
tdic[d  nums[i]] = tdic.get(d  nums[i], 0) + dic.get(d, 0)
dic = tdic
return dic.get(S, 0)
Python DP


by using dic, I count how many possible combo to reach to some val
k
, wherek
is thekey
of dic
if nums[0] != 0:
#say nums[0] == 2
dic = {2: 1, 2: 1}else:
#nums[0] == 0
dic = {0: 2}you see, if nums[0] is 0, then what I know is that there are
two
ways to reach to 0 at first step.
else if nums[0] is non0, say 2, I will know there areone
way to reach to 2 andone
way to reach to 2


@lbr This code will get keyError when
nums=[], S=1
becausememo
is not a defaultdict.