213. House Robber II

Problem Statement

link: https://leetcode.com/problems/house-robber-ii/ https://leetcode.cn/problems/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.

Example:

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

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

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

Solution Approach

Split the circular house-robbing problem into two subproblems by excluding the first and last houses. Calculate the maximum money that can be robbed for each subproblem using dynamic programming and return the maximum of these two results.

Algorithm

1. If there is only one house, return the money in that house. Otherwise, split the problem into two subproblems: robbing from the first house to the second-to-last house and robbing from the second house to the last house.
2. Create a helper function ‘maxRob’ to calculate the maximum money that can be robbed without alerting the police for a given list of money, using dynamic programming.
3. Return the maximum result between ‘maxRob(nums[0:l-1])’ and ‘maxRob(nums[1:l])’, which represents the maximum money obtained by considering both subproblems, effectively handling the circular arrangement of houses.

Implement

    # 0 ~ -1, 1 ~ l  # dp0, dp1 = dp1, max(pd0 + nums[i], dp1) class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 1:
            return nums[0]
        return max(self.maxRob(nums[0: l-1]), self.maxRob(nums[1: l]))
      
    def maxRob(self, moneys):
        dp0, dp1 = 0, 0
        for i in range(len(moneys)):
            dp0, dp1 = dp1, max(dp1, dp0 + moneys[i])
        return dp1
              

    
    

Twitter  facebook  Email