My Python DP using decorator to cache values, with explanation.


  • 1
    Z

    The formula is simple:
    Let F(n, S) be the number of solutions of a1, a2,...an with target S.
    which could be calculated by F(n-1, ) +/- a_n
    that is,
    F(n, S) = F(n-1, S+a_n) + F(n-1, S-a_n)

    as for its boundary, if a1==0, and target S=0, we got 2 solutions, +0 or -0.
    if a1>0, if a1 == abs(S) we have 1 solution.
    we got 0 solution on other condition.

    It is hard to me to write the code bottom up. So I prefer to use decorator as a cache.

    class Solution(object):
        def findTargetSumWays(self, nums, S):
            """
            :type nums: List[int]
            :type S: int
            :rtype: int
            """
            def cache(func):
                cache_ = {}
                def wrapper(*args):
                    try:
                        return cache_[args]
                    except:
                        cache_[args] = func(*args)
                        return cache_[args]
                return wrapper
    
            @cache
            def helper(n, arr, s):
                if n == 0:
                    if s == arr[n] == 0:
                        return 2
                    elif abs(s) == arr[n]:
                        return 1
                    else:
                        return 0
                else:
                    return helper(n-1, arr, s+arr[n]) + helper(n-1, arr, s-arr[n])
    
            return helper(len(nums)-1, tuple(nums), S)
    

Log in to reply
 

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