问题描述
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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
思路
类似DP的思路
第i天能拿到的钱，等于max(dp[i-1], dp[i-2]+nums[i])，因为不能连着两户都拿
注意dp[i-1]并不一定包含[i-1]这天的钱，只是到这天为止可拿到的最大值，dp[i-2]同理
因为此题只要返回最大值，可以只保留cur = dp[i-1]和pre = dp[i-2]
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length == 0:
return 0
if length == 1:
return nums[0]
pre, cur = nums[0], max(nums[0],nums[1])
for i in range(2, length):
pre, cur = cur, max(cur, pre+nums[i])
return max(pre, cur)