問題描述
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
例子

image.png

解題思路：不能闖入相鄰 的兩個房間，所以每兩個房間可以相隔一個、二個。。等多個房間，在這種情況下找到最優(yōu)值。可能有的人會說隔一個去一個，數(shù)量最多，金額肯定最高。但是如果是2 1 1 2 呢.所以我們需要使用動態(tài)規(guī)劃來遍歷所有的房間以得到最優(yōu)的值。

1動態(tài)規(guī)劃1
思路：構(gòu)建一個[None,None]N的二維數(shù)組，該數(shù)組長度為N（房間的個數(shù)）。第[i][0]存儲的是第i個房間不進(jìn)入的最優(yōu)值，。第[i][1]存儲的是第i個房間進(jìn)入*的最優(yōu)值。
直到遍歷所有房間。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums)<=2:
            return max(nums)
        dp=[[None]*2 for _ in nums]
        print(dp)
        dp[0][0]=0 #存儲的是當(dāng)前的房間不進(jìn)
        dp[0][1]=nums[0]#進(jìn)當(dāng)前的房間
        for i in range(1,len(nums)):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1])
            dp[i][1]=dp[i-1][0]+nums[i]
        n=len(nums)-1
        return max(dp[n][0],dp[n][1])

2動態(tài)規(guī)劃2
思路：構(gòu)建一個一維數(shù)組，數(shù)組存儲的是有i個房間時的最優(yōu)值。

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        if len(nums) == 0:
            return 0

        N = len(nums)
        dp = [0] * (N+1)
        dp[0] = 0#0個房間
        dp[1] = nums[0] #1個房間
        for k in range(2, N+1):
            dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])#第k個房間的最大值
        return dp[N]

3 動態(tài)規(guī)劃3
思路：只需要2個空間，第一個空間存儲的時之前的位置 的最優(yōu)值，第二個空間存儲的當(dāng)前位置的最優(yōu)值。

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev = 0#之前的的位置的最優(yōu)值
        curr = 0#當(dāng)前的位置的最優(yōu)值
    
    # 每次循環(huán)，計算“偷到當(dāng)前房子為止的最大金額”
        for i in nums:
            prev, curr = curr, max(curr, prev + i)
            # 循環(huán)結(jié)束時，curr 表示 dp[k]，prev 表示 dp[k-1]
    return curr

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/house-robber