leetcode-dp

494. Target Sum.py

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, {})