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

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

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