#coding=utf-8
# 递归1 递归到底
# 序列选与不选的模板题 o(2**n) 20190307 找工作期间
class Solution1(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
self.res = 0
if not nums or not S:
return self.res
self.trySum(nums,S,0)
print self.res
return self.res
def trySum(self,nums,target,index):
if index == len(nums)-1:
if nums[index] == target or -nums[index] == target:
self.res += 1
return
self.trySum(nums,target-nums[index],index+1)
self.trySum(nums,target+nums[index],index+1)
# s = Solution1()
#
# nums1 = [1, 1, 1, 1, 1]
# ts1 = 3
#
#
# s.findTargetSumWays(nums1,ts1)
# 递归2
# 层次递归 :不使用全局变量
class Solution2(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
if not nums or not S:
return 0
return self.trySum(nums,S,0)
def trySum(self,nums,target,index):
res = 0
if index == len(nums)-1:
if nums[index] == target or -nums[index] == target:
res += 1
return res
res += self.trySum(nums,target-nums[index],index+1)
res += self.trySum(nums,target+nums[index],index+1)
return res
# s = Solution2()
#
# nums1 = [1, 1, 1, 1, 1]
# ts1 = 3
#
#
# print s.findTargetSumWays(nums1,ts1)
#https://blog.csdn.net/qq_17550379/article/details/82939713
# 记忆化递归
class Solution3(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
if not nums :
return 0
self.memo = {}
return self.trySum(nums,S,0)
def trySum(self,nums,target,index):
pair = (index,target)
if pair in self.memo:
return self.memo[pair]
res = 0
if index == len(nums):
if target == 0:
res += 1
return res
res += self.trySum(nums,target-nums[index],index+1)
res += self.trySum(nums,target+nums[index],index+1)
self.memo[pair] = res
return res
# s = Solution3()
#
# nums1 = [1, 1, 1, 1, 1]
# ts1 = 3
#
#
# print s.findTargetSumWays(nums1,ts1)
# 动态规划
# https://blog.csdn.net/qq_17550379/article/details/82939713
# https://www.cnblogs.com/onlyac/p/6986139.html
class Solution4(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int """ total = sum(nums) memo = [[0] * (2*total+1) for i in range(len(nums) + 1)] memo[0][total] = 1 for i in range(1,len(nums)+1): for j in range(2*total+1): if j+nums[i-1] < 2*total+1: memo[i][j] += memo[i-1][j+nums[i-1]] if j-nums[i-1] >=0: memo[i][j] += memo[i-1][j-nums[i-1]] return memo[len(nums)][total+S]