-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0494 [M] Target Sum
Code with Senpai edited this page Jan 23, 2022
·
2 revisions
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)
footer