題目
難度：★★☆☆☆
類型：數(shù)學
你是一個專業(yè)的小偷僵刮，計劃偷竊沿街的房屋据忘。每間房內(nèi)都藏有一定的現(xiàn)金峡钓，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入若河，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組寞宫，計算你在不觸動警報裝置的情況下萧福，能夠偷竊到的最高金額。
示例
示例 1:
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) 辈赋，然后偷竊 3 號房屋 (金額 = 3)鲫忍。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2:
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)钥屈，接著偷竊 5 號房屋 (金額 = 1)悟民。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。
解答
這是一個典型的動態(tài)規(guī)劃問題篷就。
定義向量dp
dp向量長度與輸入數(shù)組nums相同射亏，dp[i]表示到第下標為i的房屋位置，可以打劫到的最大金額竭业；初始條件
（1）當i=0時智润，打劫到第一家為止最大的打劫金額為這一家的金額，即dp[0]=nums[0]
（2）當i=1時未辆，由于相鄰房屋不能同時打劫窟绷，因此打劫到第二家位置的最大打劫金額為前兩家中的最大值，即dp[1]=max(nums[0], nums[1])狀態(tài)轉(zhuǎn)移方程
當i>=2時咐柜，當前的總金額有兩種情況：
（1）如果打劫下標為i的房間兼蜈，這樣下標為i-1的房間不能打劫，則當前的最大總金額為打劫到i-2房間的金額與下標為i的房間的金額之和拙友；
（2）不打劫下標為i的房間为狸，則當前的最大金額等于打劫到i-1房間的最大金額；
取兩個選擇的最大值遗契，因此有：
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
具體編碼實現(xiàn)如下：
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: # 沒有家舍
return 0
if len(nums) == 1: # 只有一家
return nums[0]
dp = [0 for _ in range(len(nums))] # 定義dp
dp[0], dp[1] = nums[0], max(nums[0], nums[1]) # 并初始化
for i in range(2, len(nums)): # 從第3家開始循環(huán)到最后一家
dp[i] = max(dp[i-2]+nums[i], dp[i-1]) # 狀態(tài)轉(zhuǎn)移方程
return dp[-1] # 返回最后結(jié)果
如有疑問或建議钥平，歡迎評論區(qū)留言~
