Python 8 lines DP with Explanation


  • 0

    The idea is: For the last number, the acceptable calculation for the previous n-1 is [S-value(n), S+value(n)].

    If there are two ways to get the same acceptable calculation list, then count two as the 'path' to the sub problem. Example: the current number is 2, acceptable calculation list is [4, 8]. After the iteration, the acceptable calculation list change to [2, 6, 10] while the count of 6 is 2 since 4 + 2 or 8 -2 could get 6.

    At the end, the count of 0 in acceptable calculation list will be the answer.

    from collections import defaultdict
    
    class Solution(object):
        def findTargetSumWays(self, nums, S):
            table = {S:1}
            for i in nums:
                _table = defaultdict(int)
                for target, cnt in table.iteritems():
                    _table[target+i] += cnt
                    _table[target-i] += cnt
                table = _table
            return table[0]

Log in to reply
 

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