Python DP


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

  • 0
    Y
    This post is deleted!

  • 0
    Y

    Excellent solution!
    Could you please explain this part?

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

  • 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


  • 0
    Y

    @Ipeq1 said in Python DP:

    if nums[0] is 0,

    I got you! Thanks for the explanation!


  • 11
    L

    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]
    
    

  • 1

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


  • 0
    Z
    This post is deleted!

  • 0
    G

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


  • 0
    W
    This post is deleted!

Log in to reply
 

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