每日一題 | Python3 實(shí)戰(zhàn) LeetCode 「198. 打家劫舍 」& 「213. 打家劫舍 II」

198. 打家劫舍 & 213. 打家劫舍 II

題目鏈接

https://leetcode-cn.com/problems/house-robber/

也可以點(diǎn)擊「閱讀原文」直達(dá)題目鏈接。

題目描述

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

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

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)。
     偷竊到的最高金額 = 1 + 3 = 4

示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 1)。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

解題思路

這道題是標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃的題目。但是對(duì)于之前沒有接觸過動(dòng)態(tài)規(guī)劃或者對(duì)動(dòng)態(tài)規(guī)劃不熟悉的同學(xué)來說（比如說我），還是有一定的難度的。因此我剛開始用的是暴力搜索的方法，不出意外的超時(shí)了。后面加上剪枝的過程后，勉強(qiáng)通過。

不過呢，動(dòng)態(tài)規(guī)劃早晚都是要學(xué)的，剛好趁這個(gè)機(jī)會(huì)，也記錄下自己的學(xué)習(xí)過程。

其實(shí)動(dòng)態(tài)規(guī)劃的理論，很多人應(yīng)該都不陌生，首先是狀態(tài)定義、然后是狀態(tài)轉(zhuǎn)移方程，還有就是邊界情況。理論大家都知道，但是碰到題目的還是一臉懵逼。

我覺得出現(xiàn)這種情況的原因還是自己見的動(dòng)態(tài)規(guī)劃的題目比較少，一看到是動(dòng)態(tài)規(guī)劃的題目，就望而卻步，放棄了。

不過這次下定決心，掌握基本的算法。所以只能咬著牙堅(jiān)持下去了。

對(duì)于這道題的話，因?yàn)椴荒芡当I相鄰的房間，因此，對(duì)于當(dāng)前房間來說，如果偷盜當(dāng)前房間，那么前一個(gè)房間是不能偷盜的。

這是一個(gè)很重要的點(diǎn)，如果我們定義一個(gè)數(shù)組 dp，然后 dp[i] 表示到當(dāng)前房間所能偷盜的金額的最大值的話，那么

這就是本題的狀態(tài)轉(zhuǎn)移方程，以及狀態(tài)定義了。不要問是怎么想到的。。。

代碼

暴力搜索代碼：超時(shí)

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

    def dfs(self, index, nums, cur, res):
        if cur == len(nums):
            if res > self.ans:
                self.ans = res
            return
        if index == 0:
            self.dfs(1, nums, cur + 1, res + nums[cur])
        self.dfs(0, nums, cur + 1, res)

搜索 + 剪枝：通過

class Solution:
    def rob(self, nums: List[int]) -> int:
        self.ans = 0
        self.state = [[0 for _ in range(len(nums))] for _ in range(2)]
        print(self.state)
        if len(nums) > 0:
            self.dfs(0, nums, 1, 0)
            self.dfs(1, nums, 1, nums[0])
        return self.ans

    def dfs(self, index, nums, cur, res):
        if cur == len(nums):
            if res > self.ans:
                self.ans = res
            return
        if index == 0:
            if res + nums[cur] > self.state[1][cur - 1]:
                self.state[1][cur - 1] = res + nums[cur]
                self.dfs(1, nums, cur + 1, res + nums[cur])
        if res > self.state[0][cur - 1]:
            self.state[0][cur - 1] = res
            self.dfs(0, nums, cur + 1, res)

動(dòng)態(tài)規(guī)劃：通過

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

動(dòng)態(tài)規(guī)劃 + 空間優(yōu)化：通過

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        size = len(nums)
        if size == 1:
            return nums[0]
        first, second = 0, nums[0]
        for i in range(2, size + 1):
            first, second = second, max(second, first + nums[i - 1])
        return second

復(fù)雜度分析

這里只對(duì)動(dòng)態(tài)規(guī)劃解法進(jìn)行分析。

動(dòng)態(tài)規(guī)劃：

時(shí)間復(fù)雜度：

空間復(fù)雜度：

動(dòng)態(tài)規(guī)劃 + 空間優(yōu)化

時(shí)間復(fù)雜度：

空間復(fù)雜度：

另外，力扣上還有一道題，是這道題的升級(jí)版，它就是 「213.打家劫舍II」,題目鏈接如下：

https://leetcode-cn.com/problems/house-robber-ii/

這道題比上個(gè)題目多的要求就是這次的屋子假是首尾相連的，也就是說偷盜第一間房屋的話，就不能偷盜最后一間房屋了（只有一間房屋的時(shí)候除外），因此我們可以將這次的偷盜看成兩部分來進(jìn)行看待，第一部分就是只偷盜除了最后一間屋子時(shí)的情況，第二種情況就是不考慮偷盜第一間屋子，只考慮偷盜剩下的屋子。然后這兩部分的最大值就是結(jié)果。

代碼

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        size = len(nums)
        if size == 1:
            return nums[0]
        return max(self.rob_(nums[:-1]), self.rob_(nums[1:]))


    def rob_(self, nums: List[int]) -> int:
        if not nums:
            return 0
        size = len(nums)
        if size == 1:
            return nums[0]
        first, second = 0, nums[0]
        for i in range(2, size + 1):
            first, second = second, max(second, first + nums[i - 1])
        return second

復(fù)雜度分析

時(shí)間復(fù)雜度：

空間復(fù)雜度：

好了，今天的內(nèi)容就到這里了。我最近在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的相關(guān)知識(shí)，也會(huì)在力扣進(jìn)行每日一題的打卡。如果你最近在求職面試或者也在進(jìn)行力扣進(jìn)行每日一題的打卡的話，歡迎加入我們，后臺(tái)回復(fù)「加群」即可。我一直堅(jiān)信一個(gè)人走的更快，一群人走的更遠(yuǎn)。很多時(shí)候，只要堅(jiān)持下去了，那么你就超越了很多人。

參考資料

• https://leetcode-cn.com/problems/house-robber/solution/yu-ni-yi-qi-xue-suan-fa-python3-shi-xian-knk6/
• https://leetcode-cn.com/problems/house-robber-ii/solution/yu-ni-yi-qi-xue-suan-fa-python3-shi-xian-ifpb/
• https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/