Concise python DP solution

  • 0

    top-down from S works fine instead of bottom up from 0.
    Other than that this is a typical DP solution.

    def findTargetSumWays(self, nums, S):
        self.dp = [defaultdict(int) for i in range(len(nums))]
        return self.get_ways(nums, S, len(nums)-1)
    def get_ways(self, nums, S, i):
        if i == -1:
            return 1 if S == 0 else 0        
        if S not in self.dp[i]:
            self.dp[i][S] = self.get_ways(nums, S + nums[i], i - 1) + self.get_ways(nums, S - nums[i], i - 1)
        return self.dp[i][S]

    Thank you.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.