# Python DP

• ``````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)
``````

• This post is deleted!

• Excellent solution!
Could you please explain this part?

``````dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0: 2}
``````

• @yangxuserene

by using dic, I count how many possible combo to reach to some val `k`, where `k` is the `key` 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 non-0, say 2, I will know there are `one` way to reach to -2 and `one` way to reach to 2

• @Ipeq1 said in Python DP:

if nums[0] is 0,

I got you! Thanks for the explanation!

• Same idea a bit tidier.

``````class Solution(object):
def findTargetSumWays(self, nums, S):
from collections import defaultdict
memo = {0: 1}
for x in nums:
m = defaultdict(int)
for s, n in memo.iteritems():
m[s + x] += n
m[s - x] += n
memo = m
return memo[S]

``````

• @lbr I like the way you coded for this problem.

• This post is deleted!

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

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.