Leetcode 198. House Robber

Problem

Leetcode 198 - House Robber

Example:

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 = [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.

Approach

We can use dynamic programming to solve this. Since the robber can’t rob houses that are adjacent, Our base case would be dp[0] = nums[0], dp[1] = nums[1], dp[2] = nums[2] + dp[0], and so forth. Thus the maximum amount robber can rob would be nums[i] + max(dp[i-2], dp[i-3]).

Then in the end, we can return the max of last two elements in dp array.

Here is the Python code for the solution:

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

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

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$