- 分類：Backtracking/DP
- 時間復雜度: O(n)
- 空間復雜度: O(n)->O(1)
198. House Robber
你是一個專業(yè)的小偷辆琅，計劃偷竊沿街的房屋蝗羊。每間房內都藏有一定的現(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 折汞。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/house-robber
著作權歸領扣網(wǎng)絡所有倔幼。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處字支。
代碼1：
class Solution:
def rob(self, nums: List[int]) -> int:
res = 0
if nums == None or len(nums)==0:
return res
dp = [0 for i in range(len(nums)+2)]
for i in range(2,len(nums)+2):
dp[i]=max(dp[i-2]+nums[i-2],dp[i-1])
return dp[-1]
代碼2：
class Solution:
def do_rob(self, nums, i, memo):
if i<0:
memo[i] = 0
return 0
if i in memo:
return memo[i]
memo[i]= max(self.do_rob(nums,i-2,memo)+nums[i],self.do_rob(nums,i-1,memo))
return memo[i]
def rob(self, nums: List[int]) -> int:
res = 0
if nums == None or len(nums)==0:
return res
memory = dict()
return self.do_rob(nums,len(nums)-1,memory)
討論：
1.對于每一個房子我們有2種選擇
- take the money if we didn't robber house i-1
- skip it
dp or do_rob(n)代表的是該時刻能搶到的最多的錢的時候
