The title

A professional thief, planning to rob houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on theft is that adjacent houses are connected with an anti-theft system, which will automatically alarm if two adjacent houses are broken into on the same night.

Given a numS array of non-negative integers representing the amount stored in each house, calculate the maximum amount of money that can be stolen in one night without setting off the alarm.

 

Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Steal House 1 (amount = 1), then steal House 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Steal House 1 (amount = 2), House 3 (amount = 9), then House 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.Copy the code

Tip:

1 <= nums.length <= 100 0 <= nums[i] <= 400

Their thinking

Class Solution: def rob(self, nums: [int]) -> int: dp = [0]* nums == 1 return nums[0] elif len(nums) == 2: return max(nums[0],nums[1]) 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]) # print(dp) return dp[-1] if __name__ == "__main__": Nums = [2,7,9,3,1] NUMs = [1, 2, 3,1] RET = Solution(). Print (ret)Copy the code