Python 2 Clean DP Solutions Comparison w/ inline comment explanation


  • 1
    V

    Faster/More efficient method. Less intuitive, relies on weird method of going through weights in reverse on the inner loop to avoid overwriting prior outer loop iteration's dp[j] calculations.

    class Solution(object):
        # this is an application of knapsack problem, where w=sum(nums)/2
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            isum = sum(nums)
            
            # if weight not divisible by two, we cannot possibly have two equal sets
            if isum % 2 != 0:
                return False
            
            # isum is weight
            isum /= 2
            
            # dp init
            dp = [False for j in xrange(isum + 1)]
            dp[0] = True
            
            # j is weight bound, and i is arr pointer.
            # dp[j] :: for a weight j, can we partition into two equal sets with elements 0..i
            for i in xrange(len(nums)):
                # reversal neessary, because if we go in non-reversed order, we will overwrite 
                # dp[] calculations from the previous iteration of outer loop. thus we go small to big to preserve previous iteration
                for j in reversed(xrange(1, isum + 1)):
                    if j - nums[i] >= 0:
                        dp[j] = dp[j] or dp[j - nums[i]]
    
            return dp[isum]
            
            
    

    Slightly less efficient, still same complexity at O(n^2)... More intuitive and straight forward in my opinion. This i my preferred solution.

    class Solution(object):
        # this is an application of knapsack problem, where w=sum(nums)/2
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            isum = sum(nums)
            
            # if weight not divisible by two, we cannot possibly have two equal sets
            if isum % 2 != 0:
                return False
            
            # isum is weight
            isum /= 2
            
            # dp init
            dp = [[False for j in xrange(isum + 1)] for i in xrange(len(nums) + 1)]
    
            for i in xrange(len(nums) + 1):
                for j in xrange(isum + 1):
                    if i == 0 and j == 0: # base case, nothing to select with, and 0 weight
                        dp[i][j] = True
                    elif i == 0: # i == 0 signifies base case where we select nothing, we can never achieve any non-zero goal
                        dp[i][j] = False
                    elif j == 0: # we can always achieve weight goal of 0, just select nothing.
                        dp[i][j] = True
                    else: # dp transition step
                        if j >= nums[i - 1]: # do a weight bounds check, then check both possibilities of both including and excluding the current element nums[i - 1]
                            dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
                        else:
                            dp[i][j] = dp[i - 1][j]
    
            return dp[len(nums)][isum]
            
            
    

Log in to reply
 

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