Python DP solution, faster than the other method of prev_max and curr_max


  • 0
    M
    class Solution(object):
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
            if len(nums) == 0:
                return 0
            elif len(nums) == 1:
                return nums[0]
            
            houses = {-1:0, 0:nums[0]}
            
            for i in range(len(nums[1:])):
                real_i = i + 1
                
                if houses[real_i - 2] + nums[real_i] > houses[real_i - 1]:
                    houses[real_i] = houses[real_i - 2] + nums[real_i]
                else:
                    houses[real_i] = houses[real_i - 1]
            
            return houses[len(nums) - 1]
    

    I've run the other 3 line solution and also the model solution from the solution page with prev_max and curr_max but they were slower than my entry. I'm wondering why though... Any guesses?


Log in to reply
 

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