---

一、198. 打家劫舍

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

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

1、動態規劃五部曲

1、確定dp數組（dp table）以及下標的含義
dp[i]：考慮下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]。

2、確定遞推公式
決定dp[i]的因素就是第i房間偷還是不偷。
如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考慮的，找出 下標i-2（包括i-2）以內的房屋，最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。
如果不偷第i房間，那么dp[i] = dp[i - 1]，即考 慮i-1房，（注意這里是考慮，并不是一定要偷i-1房，這是很多同學容易混淆的點）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3、dp數組如何初始化
從遞推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，遞推公式的基礎就是dp[0] 和 dp[1]
從dp[i]的定義上來講，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

# 3、數組初始化
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

4、確定遍歷順序
dp[i] 是根據dp[i - 2] 和 dp[i - 1] 推導出來的，那么一定是從前到后遍歷！

class S198:def func(self, nums):# 1、創建dp數組，dp[i]:到達下標為i的位置偷竊的最大金額dp = [0] * (len(nums))# 3、數組初始化dp[0] = nums[0]dp[1] = max(nums[0], nums[1])# 4、確定遍歷順序for i in range(2, len(nums)):# 2、確定遞推公式dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])print(dp)return dp[-1]r = S198()
nums = [2, 7, 9, 3, 1]
print(r.func(nums))

二、213. 打家劫舍 II

中等

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

對于一個數組，成環的話主要有如下三種情況：
情況一：考慮不包含首尾元素

情況二：考慮包含首元素，不包含尾元素

情況三：考慮包含尾元素，不包含首元素

注意我這里用的是"考慮"，例如情況三，雖然是考慮包含尾元素，但不一定要選尾部元素！ 對于情況三，取nums[1] 和 nums[3]就是最大的。

而情況二 和 情況三 都包含了情況一了，所以只考慮情況二和情況三就可以了。

class S213:def func(self, nums):if not nums:return 0if len(nums) <= 2:return max(nums)# 1、創建dp數組，明確dp數組的含義,之前房間到i時偷的最大金幣為dp[i]dp = [0] * len(nums)# dp[i]:含義 第i個數偷的最高金額# todo 搶第一個房間，不搶最后一個房間dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, len(nums) - 1):# 2、確定遞推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])res1 = dp[-2]print(dp)  # [1, 2, 4, 0]dp1 = [0] * len(nums)# todo 不搶第一個房間，搶最后一個房間dp1[0] = 0dp1[1] = nums[1]dp1[2] = max(nums[1], nums[2])for i in range(3, len(nums)):# 2、確定遞推公式dp1[i] = max(dp1[i - 2] + nums[i], dp1[i - 1])res2 = dp1[-1]print(dp1)  # [0, 2, 3, 3]return max(res1, res2)r = S213()
nums = [1, 2, 3, 1]
print(r.func(nums))

---