Skip to content
{{ message }}

Instantly share code, notes, and snippets.

liyunrui/494. Target Sum.py

Created Feb 27, 2021
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, {})
to join this conversation on GitHub. Already have an account? Sign in to comment