打家劫舍I#IT人的升職加薪tips#

關注公衆号【程式員學長】，回複【電子書】，免費獲得上百本計算機經典書籍

打家劫舍I

問題描述

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。

示例：

輸入：[1，2，3，1]

輸出：4

解釋：偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

分析問題

首先，我們先将問題簡化處理。假設目前隻有一間房屋，則偷竊該房屋，此時就是偷竊到的最高總金額。如果隻有兩間房屋，因為此時兩間房屋相鄰，隻能偷竊其中的一間房屋，可以選擇其中金額較高的房屋進行偷竊，就是可以偷竊到的最高總金額。如果房屋的數量大于兩間，假設小偷此時處于第k（k>2）間房屋，那麼他有兩個選擇。

• 如果他偷竊第k間房屋，那麼他就不能偷竊第k-1間房屋，此時其能偷竊到的總金額為前k-2間房屋的最高總金額和第k間房屋的金額之和。
• 如果他不偷竊第k間房屋，那麼此時其能偷竊到的總金額為前k-1間房屋的最高總金額。

在上述兩個選項中選擇金額較大的即為前k間房屋能偷竊到的最高總金額。

我們用 dp[i] 來表示前 i 間房屋能偷竊到的最高總金額，經過前面的分析，可以知道其狀态轉移方程為：

dp[i] = max( dp[i-2] + nums[i] , dp [i-1])

下面我們來看一下邊界條件。

• 當隻有一間房屋時，此時dp[0] = nums[0]，表示偷竊該房屋。
• 當隻有兩間房屋時，此時 dp[1] = max(nums[0] , nums[1])，即在這兩間房屋中選擇金額較大的房屋進行偷竊。

下面我們來看一下代碼的實作。

class Solution:
    def rob(self, nums):
        #如果數組為空，則直接傳回0
        if not nums:
            return 0
        
        length = len(nums)
        #如果房屋數量等于1
        #則直接偷竊第一間房屋，
        #是以此時能偷竊到的最大金額是nums[0]
        if length == 1:
            return nums[0]
        dp = [0] * length
        #邊界條件
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, length):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        
        return dp[length - 1]      

該算法的時間複雜度是O(n)，空間複雜度也是O(n)。

通過觀察，我們發現dp[i] 隻和 dp[i-2] 和 dp[i-1]有關，即隻和該房屋的前兩間房屋的最高總金額相關，是以我們可以使用滾動數組，在每個時刻隻需要存儲前兩間房屋的最高總金額即可，進而降低空間複雜度。我們來看一下代碼的實作。

class Solution:
    def rob(self, nums):
        #如果數組為空，則直接傳回0
        if not nums:
            return 0


        length = len(nums)
        #如果房屋數量等于1
        #則直接偷竊第一間房屋，
        #是以此時能偷竊到的最大金額是nums[0]
        if length == 1:
            return nums[0]
            
        #邊界條件
        first, second = nums[0], max(nums[0], nums[1])
        
        for i in range(2, length):
            first, second = second, max(first + nums[i], second)
        
        return second