Post

Leetcode 213. House Robber II

Explanation for Leetcode 213 - House Robber II, and its solution in Python.

Posted
By Hyeonu(Eric) Kim
1 min read

Problem

Leetcode 213 - House Robber II

Example:

1
2
3
4
5
6
7
8
9
10
11

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Input: nums = [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.

Input: nums = [1,2,3]
Output: 3

Approach

Since we can’t rob a house at nums[0] and nums[-1], we can find the max of nums[1:] and nums[:-1].

Here is the Python code for the solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        return max(self.helper(nums[1:]), self.helper(nums[:-1]))
    
    def helper(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        
        return dp[-1]

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$

Leetcode, Dynamic Programming, Medium
Leetcode Python Dynamic Programming Medium
This post is licensed under CC BY 4.0 by the author.