題目鏈接
難度： 簡單 ??????類型：動態(tài)規(guī)劃
你是一個專業(yè)的小偷渤刃，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金略号，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入玄柠，系統(tǒng)會自動報警诫舅。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下刊懈，能夠偷竊到的最高金額娃闲。
示例
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)匾浪，接著偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 蛋辈。
解題思路
- dp[i]的含義為到第i家店小偷能偷到的最高金額
- 到第i家店時有兩種可能性，一是偷梯浪，二是不偷，為了不會報警礼预，偷時必須保證i-1家店沒被偷虏劲，該情況偷得得金額為dp[i-2]+nums[i]，若不偷柒巫，此時得金額等于dp[i-1]
- 得到狀態(tài)轉(zhuǎn)移方程： dp[i] = max(dp[i-2]+nums[i], dp[i-1])
代碼實現(xiàn)
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
elif len(nums)<=2:
return max(nums)
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
dp[1] = max(nums[:2])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
return dp[i]
