LeetCode Day 48 (Day 47 is rest day) Dynamic Programming (9/17)

Today we move to a new questions: House robber

Question 1

198. House Robber

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Intuition tells me that there might be some greedy problems involved, and that to ensure the greatest benefit, one might want to look for the place with the most money to make the first move. And whether the current house is stolen or not depends on, whether the previous house and the previous two houses were stolen.

It can still be solved using dynamic programming in five parts.

1. Determine the dp array (dp table) and the meaning of the subscripts
   1. dp[i]: consider the houses up to and including subscript i. The maximum amount that can be stolen is dp[i].
2. Determine the recursive formula
   1. The factor that determines dp[i] is whether room i is stolen or not. If room i is stolen, then dp[i] = dp[i - 2] + nums[i], i.e., room i-1 must be disregarded, and find the houses up to subscript i-2 (and including i-2) for which at most the amount of money that can be stolen is dp[i-2] plus the amount of money that was stolen from room i.
   2. If room i is not stolen, then dp[i] = dp[i - 1], i.e., room i-1 is considered, and then dp[i] is taken to be the maximum value, i.e., dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3. How the dp array is initialised
   1. From the recursive formula dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); you can see that the recursive formula is based on dp[0] and dp[1]
   2. From the definition of dp[i], dp[0] must be nums[0] and dp[1] is the maximum of nums[0] and nums[1] i.e.: dp[1] = max(nums[0], nums[1]);
4. Determine the traversal order
   1. dp[i] is derived from dp[i - 2] and dp[i - 1], so it must be traversed from front to back!
5. Example of deriving the dp array

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:  
            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 - 2] + nums[i], dp[i - 1])
 
        return dp[-1] 

Question 2

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Compare this question with the previous one, which becomes a ring, and you need to consider the following three factors:

For an array, there are three main cases if it becomes a ring as follows:

Case 1: Consider an array that does not contain the first and last elements Case 2: Consider an array that contains the first element but not the last element. Case 3: Consider an array with a tail element and no head element.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: 
            return 0
 
        if len(nums) == 1:  # If just one house
            return nums[0]
 
        # Case 2: dont rob first house
        prev_max = 0  
        curr_max = 0  
        for num in nums[1:]:
            temp = curr_max  
            curr_max = max(prev_max + num, curr_max)  
            prev_max = temp  
        result1 = curr_max
 
        # Case 3: Dont rob last house
        prev_max = 0  
        curr_max = 0 
        for num in nums[:-1]:
            temp = curr_max  
            curr_max = max(prev_max + num, curr_max)  
            prev_max = temp  
        result2 = curr_max
 
        return max(result1, result2)

Question 3

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

This question must be about backward traversal, because the return value of the recursive function is used to do the next calculation.

class Solution:
    def rob(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if root.left is None and root.right  is None:
            return root.val
        # rob parent node
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        # Do not rob parent node
        val2 = self.rob(root.left) + self.rob(root.right)
        return max(val1, val2)