Leetcode 198. House Robber (Python)

Related Topic

Dynamic-Programming.

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Sample I/O

Example 1

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).Total amount you can rob = 2 + 9 + 1 = 12.

Methodology

This question solved by Dynamic Programming. It is similar with question 746 Min Cost Climbing Stairs. For min cost climbing stairs qusetion, each time you can either climb 1 or 2 steps and each move you will pick the min cost from last two steps. For this question, you can rob the adjacent house means you have to skip the last step and pick the maximum money between the forth and the third from last.

1. The base case:
   1. If you need a dp list
      1. dp[0]=0
      2. dp[1]=nums[0]
   2. Or you can just modify the original list
      1. nums=[0]+nums

2. Find the pattern:

   Start from the forth position and pick the maxmium value between the forth and the third from last. Then sum up to the current value to get the current position’s maximum value

3. Result Because you can rob the adjacent house, so the final answer should be the mixmium value picked between the last and the second last value

Code 1 (Modify the original list)

def rob(self, nums: List[int]) -> int:
    if not nums: return 0
            nums = [0]+nums
            for i in range(3,len(nums)):
                nums[i]+=max(nums[i-3],nums[i-2])
            return max(nums[-1],nums[-2])

Code 2 (Not modify the original list)

def rob(self, nums: List[int]) -> int:
    if not nums: return 0
        size=len(nums)
        if size < 3:
            return max(nums)
        dp=[0]*(size+1)
        dp[1]=nums[0]
        dp[2]=nums[1]
        for i in range(2,size):
            dp[i+1]=nums[i]+max(dp[i-2],dp[i-1])
        return max(dp[-2],dp[-1])

BigO

We iterate all dp array, it will cost O(n), each value will add up last two value as result, it will cost (1+2), in total will be O(n+2n) and It is O(n)