Intuitive Python DP Solution (one loop)


  • 0
    A

    Two cases:

    1. Don't rob last house, then it becomes a House Robber I problem from House 1 to House n-1.
    2. Don't rob first house, then it becomes a House Robber I problem from House 2 to House n.
    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];
            elif len(nums) == 2:
                return max(nums[0],nums[1]);
            elif len(nums) == 3:
                return max(nums[0],nums[1],nums[2]);
                
            dp1 = [0] * (len(nums)-1);
            dp2 = [0] * (len(nums)-1);
    
            dp1[0] = nums[0];
            dp1[1] = max(nums[0],nums[1]);
            dp2[0] = nums[1];
            dp2[1] = max(nums[1],nums[2]);
    
            for i in xrange(2,len(nums)-1):
                dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i]);
                dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i+1]);
            
            return max(dp1[-1],dp2[-1]);
           
    

  • 0
    S

    why dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i+1]);?

    according to your description, shouldn't it be dp2[i+1] = max(dp2[i-1],dp2[i-2]+nums[i+1]);


  • 0
    A

    @hamster "dp1" and "dp2" have same size, the only difference is how to capture the previous house from "nums" because they have different starts (i.e. dp1[0] refers to House 1 which is nums[0], dp2[0] refers to House 2 which is nums[1]).


Log in to reply
 

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