LC 0494 [M] Target Sum - ALawliet/algorithms GitHub Wiki
https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions. https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns
cache the total pos ways + neg ways
class Solution:
def findTargetSumWays(self, nums, S):
self.memo = {}
def dp(i, cur_sum):
if (i, cur_sum) in self.memo:
return self.memo[(i, cur_sum)]
# base cases
if i < 0 and cur_sum == S:
return 1
elif i < 0:
return 0
# decisions
else:
pos_ways = dp(i-1, cur_sum + nums[i])
neg_ways = dp(i-1, cur_sum + -nums[i])
self.memo[(i, cur_sum)] = pos_ways + neg_ways
return self.memo[(i, cur_sum)]
return dp(len(nums) - 1, 0)