LeetCode 198. House Robber

problem link

Key ideas:

• we can not access adjacent index
  • If we don't have this limitation, the optimal amount of money we can rob at a given index is the sum of all the values before this index
  • because of the limitation, the optimal amount of money we can rob at index 2 is nums[2] + nums[0], not nums[2] + nums[1] + nums[0]
• Wait! There is a trap though. It's naive(but incorrect) to think the optimal value of a given index is nums[index] + nums[index - 2]. Think of this input: [10, 1, 5, 4]
  • when we calculate the optimal value of index 3(whose value is 4), if we just do nums[3] + nums[1], we will get 4 + 1 = 5
  • however, as you can see, the value of nums[0] is way bigger than nums[1], and jumping to index 3 from index 0 doesn't break the rule that we can not access adjacent index, therefore the optimal value of nums[3] is nums[3] + nums[0], not nums[3] + nums[1]
• deduce from the above ideas, the optimal amount of money we can rob at a given index is either nums[index] + nums[index - 2] or nums[index] + nums[index - 3]
  • we don't need to consider nums[index - 4] and indices even smaller, because the "impact" of nums[index - 4] is already reflected in nums[index - 2], and the impact of nums[index - 5] is reflected in nums[index - 3], so on and so forth.
• the final optimal amount of money we can get is either nums[-1] or nums[-2]

Edge cases:

• length of nums could be <= 3, which will lead to index error when we access nums[index - 3]

Let's code up:

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

Result:

Runtime: 36 ms, faster than 74.71% of Python3 online submissions for House Robber.
Memory Usage: 13.9 MB, less than 67.67% of Python3 online submissions for House Robber.