問題描述
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.
補充說明：
很有趣的一個題目，假設(shè)你是一個江洋大盜梅鹦，現(xiàn)在你在一個獨立的街區(qū)裆甩，有這么一排房子，每個房子里面擁有不同價值的
財富齐唆。進入房子去盜取這些財物嗤栓，需要注意的是相鄰的兩個房子被盜就會觸發(fā)警報招來警察。試問箍邮，你在不被發(fā)現(xiàn)的情況下可以盜取的最大財物價值多少茉帅？
方案分析
- 首先明確一點，相鄰的兩個房子不能被盜竊锭弊。
- 盜竊第i個房子的時候担敌，前面的第i-1個房子有兩種狀態(tài)：第i-1個房子已被盜取，第i-1個房子未被盜取廷蓉。
- 這里需要記錄兩個值全封，rob，not_rob：rob記錄的是上一個房子被盜竊的后擁有的價值桃犬，not_rob記錄的是上一個房子沒被盜竊擁有的價值刹悴。
- 同理，對待第i個房子的時候攒暇，這次盜竊可能存在兩個結(jié)果：盜取第i個房子土匀，不盜取第i個房子。
- 綜上所述形用，該輪第i個房子是否被盜取的狀態(tài)取決于第i-1個房子的狀態(tài)就轧。
先評估本輪盜竊第i個房子的時候，那么上一個房子不能被盜田度，那么本輪操作完成妒御，能獲取的價值是not_rob + 當(dāng)前第i個房子的價值。
如果本輪不盜竊第i個房子的時候镇饺，則需要更新not_rob乎莉，未盜竊第i-1的價值和盜竊第i-1的價值中較大的那個值（因為此時本輪沒盜竊，上面那輪盜竊不盜竊都不會觸發(fā)警報）。
同理更新rob惋啃，表示盜竊第i個房子的價值哼鬓。 - 通過這個兩個值以及前面3、 4描述的限制边灭，就能限定警報的發(fā)生异希。
python實現(xiàn)
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
rob, not_rob = 0, 0
for num in nums:
cur_rob = not_rob + num # 如果盜竊這個房子，那么上一個房子必須沒有被盜竊绒瘦，否則會觸發(fā)警報称簿。
not_rob = max(not_rob, rob) # 如果這個房子沒有被盜竊，那么盜竊的最大值必須是盜竊這個房子之前那些房子盜竊到的最大值椭坚。
rob = cur_rob # 如果這個房子被盜予跌，則將這個盜竊后的值計入到rob中搏色。
return max(rob, not_rob)
