你是一個專業(yè)的小偷砖瞧，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金嚷狞，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)块促，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警床未。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組竭翠，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額薇搁。
示例 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 宏娄。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 400
動態(tài)規(guī)劃
定義子問題问裕，寫出子問題的遞推關(guān)系，確定 DP 數(shù)組的計算順序绝编，空間優(yōu)化
class Solution:
def rob(self, nums: List[int]) -> int:
prev = 0
curr = 0
# 每次循環(huán)僻澎，計算“偷到當(dāng)前房子為止的最大金額”
for i in nums:
# 循環(huán)開始時，curr 表示 dp[k-1]十饥，prev 表示 dp[k-2]
# dp[k] = max{ dp[k-1], dp[k-2] + i }
prev, curr = curr, max(curr, prev + i)
# 循環(huán)結(jié)束時窟勃，curr 表示 dp[k]，prev 表示 dp[k-1]
return curr
動態(tài)規(guī)劃+貪心算法
class Solution:
def rob(self, nums: List[int]) -> int:
a, b = 0, 0
for i in nums:
a, b = b, max(b, a+i)
return b
來源：力扣（LeetCode）
