Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-dp
class Solution:
"""
To clarify:
what's range of S?
what's range of nums? sum(nums) <= 1000 and len(nums) <= 20
"""
def findTargetSumWays(self, nums: List[int], S: int) -> int:
"""
Brute Force
T:O(2^n)
"""
self.count = 0
def dfs(i, nums, cur_sum, S):
if i ==len(nums):
if cur_sum == S:
self.count += 1
return
dfs(i+1, nums, cur_sum+nums[i], S)
dfs(i+1, nums, cur_sum-nums[i], S)
dfs(0, nums, 0, S)
return self.count
def findTargetSumWays(self, nums: List[int], S: int) -> int:
"""
DP-> Top-Down + Cache
T:O(n*2M) where n = len(nums) and M = sum(nums)
->n comes from depth of recursion tree
->M comes from 全部取+
->2 comes from 全部取-
去思考最多我們要計算多少種key在我們memo裡面.就是Time complexity.
S:O(n*2M)
"""
def dfs(i, nums, cur_sum, S, memo):
key = (i, cur_sum)
if key in memo:
return memo[key]
if i ==len(nums):
if cur_sum == S:
return 1
else:
return 0
plus = dfs(i+1, nums, cur_sum+nums[i], S, memo)
minus = dfs(i+1, nums, cur_sum-nums[i], S, memo)
memo[key] = plus+minus
return memo[key]
return dfs(0, nums, 0, S, {})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment