【LetMeFly】213.打家劫舍 II：動動態(tài)規(guī)劃

力扣題目鏈接：https://leetcode.cn/problems/house-robber-ii/

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

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

?

示例?1：

輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。

示例 2：

輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）。偷竊到的最高金額 = 1 + 3 = 4 。

示例 3：

輸入：nums = [1,2,3]
輸出：3

?

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

方法一：動態(tài)規(guī)劃

假設不考慮“環(huán)形”，那么我們應該怎么做？

很簡單，遍歷數(shù)組，使用兩個變量lastRob和lastNot分別代表上次是否打劫了。

• 如果上次打劫了，那么這次就不能打劫（$thisNot=\max (lastRob,lastNot)$）
• 如果上次沒打劫，那么這次就打劫（$thisRob=lastNot+nums[i]$）

然后更新lastRob和lastNot為thisRob和thisNot。

最終返回lastRob和lastNot的最大值即為答案。

加上環(huán)形這一限制，應怎么處理？

很簡單，環(huán)形的唯一限制就是：打劫第一家的話不能打劫最后一家，打劫最后一家的話不能打劫第一家。

因此，在$[0,len(nums)?1]$和$[1,len(nums)]$中分別求一次，取最大即可。

• 時間復雜度$O(len(nums))$
• 空間復雜度$O(1)$

AC代碼

C++

class Solution {
private:int realRob(vector<int>& nums, int l, int r) {int lastRob = nums[l], lastNot = 0;for (int i = l + 1; i < r; i++) {int newRob = lastNot + nums[i], newNot = max(lastRob, lastNot);lastRob = newRob, lastNot = newNot;}return max(lastRob, lastNot);}
public:int rob(vector<int>& nums) {if (nums.size() == 1) {return nums[0];}return max(realRob(nums, 0, nums.size() - 1), realRob(nums, 1, nums.size()));}
};

Python

# from typing import Listclass Solution:def realRob(self, nums: List[int], l: int, r: int) -> int:lastRob, lastNot = nums[l], 0for i in range(l + 1, r):lastRob, lastNot = lastNot + nums[i], max(lastNot, lastRob)return max(lastRob, lastNot)def rob(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]return max(self.realRob(nums, 0, len(nums) - 1), self.realRob(nums, 1, len(nums)))

同步發(fā)文于CSDN，原創(chuàng)不易，轉載經(jīng)作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132945449