打家劫舍Ⅱ

題目要求

解題思路

• [打家劫舍Ⅱ]是說兩個(gè)相鄰的房間不能同時(shí)偷，并且首尾兩個(gè)房間是相鄰的（不能同時(shí)偷首尾房間）
• 明顯是基于[打家劫舍Ⅰ]做的升級。[打家劫舍Ⅰ]也是說兩個(gè)相鄰的房間不能同時(shí)偷，但是首尾房間不是相鄰的（可以同時(shí)偷首尾房間）

所以，我們先從[打家劫舍Ⅰ]開始說起。

打家劫舍Ⅰ

題目：兩個(gè)相鄰的房間不能同時(shí)偷，首尾房間不相鄰，求小偷能獲取的最大金額。
對于[求數(shù)組中按照某種方法進(jìn)行選擇，求最值，而不用知道具體選擇方案]的問題，可以考慮動態(tài)規(guī)劃。動態(tài)規(guī)劃最基本的是[狀態(tài)的定義]，然后比較困難的是[狀態(tài)轉(zhuǎn)移方程]。
[狀態(tài)定義]即dp[i]，一般可以根據(jù)題意，題目要求什么，我們就定義什么。比如本題，我們定于dp[i]為數(shù)組的前i個(gè)元素中按照[兩個(gè)相鄰的房間不能同時(shí)偷]的方法，能夠獲得到的最大值。（經(jīng)驗(yàn)：定義dp[i]為數(shù)組的前i個(gè)元素的結(jié)果）
考慮[狀態(tài)轉(zhuǎn)移方程]是，一定要想辦法讓dp[i]能夠基于dp[0~i-1]生成。本題要求不能同時(shí)偷相鄰的房間。所以，dp[i]有兩種選擇：num[i]選或者不選。

• 如果num[i]選，那么由于不能選擇相鄰的房間，所以不可以選擇num[i-1]，所以選擇num[i]的情況下，數(shù)組的前i個(gè)元素構(gòu)成的最大值dp[i]=dp[i-2]+num[i];
• 如果num[i]不選，那么就可以選擇num[i-1]，所以數(shù)組的前i個(gè)元素構(gòu)成的最大值 等于 數(shù)組前i-1個(gè)元素構(gòu)成的最大值，即dp[i]=dp[i-1]
• 所以，最終的dp[i]是上面兩種情況的最大值。

[初始條件]比較簡單：

• dp[0] = num[0]
• dp[1] = max(dp[0],num[1]) = max(num[0], num[1])

[返回結(jié)果]，可以根據(jù)我們的dp[i]知道最終要求的是在整個(gè)數(shù)組上能夠取得的最大值。所以返回dp[N-1]

打家劫舍Ⅱ

在多了數(shù)組的開頭和結(jié)尾是相鄰的情況下，也就是說，數(shù)組的開頭和結(jié)尾元素不能同時(shí)選。由于狀態(tài)轉(zhuǎn)移方程中，是沒有標(biāo)記我們到底選了哪些元素的。所以如果想通過狀態(tài)轉(zhuǎn)移方程，來實(shí)現(xiàn)首尾元素不能同時(shí)選，是很難的。
這里就用上了技巧，分為兩種情況去考慮：分別在nums[0:N-1]上計(jì)算能獲得到的最大值，這兩種個(gè)情況取最大。這肯定能保證在物理上隔離了首尾兩個(gè)元素，肯定不會同時(shí)選到。

代碼

class Solution:
    def rob(self, nums: List[int]) -> int:
        N = len(nums)
        if not nums:
            return 0
        if N == 1:
            return nums[0]
        return max(self.rob1(nums[0:N - 1]), self.rob1(nums[1:N]))
    def rob1(self,nums:List[int]):    
        N = len(nums)
        if not nums:
            return 0
        if N == 1:
            return nums[0]
        # max amount [0, i]
        dp = [0] * N
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, N):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return dp[-1]

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(N)$
空間復(fù)雜度：$O(1)$文章來源地址http://www.zghlxwxcb.cn/news/detail-795961.html

到了這里，關(guān)于算法第十八天-打家劫舍Ⅱ的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！