摘要：打家劫舍打家劫舍問題描述問題描述你是一個專業的小偷，計劃偷竊沿街的房屋。給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，今晚能夠偷竊到的最高金額。和分別表示的左右孩子。

打家劫舍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[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

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

打家劫舍II

問題描述

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

示例：

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

輸出：3

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

分析問題

這道題和上一道的不同之處在于房屋的首尾是相連的，即第一間房屋和最后一間房屋是相鄰的，因此它們不能被同時偷竊。

我們也可以和上一道題的思路一樣，采用動態規劃的方法來求解。首先先將問題簡單化，假設此時只有一間房屋，則偷竊該房屋，此時就是偷竊到的最高總金額。如果只有兩間房屋，因為此時兩間房屋相鄰，只能偷竊其中的一間房屋，可以選擇其中金額較高的房屋進行偷竊，就是可以偷竊到的最高總金額。

到這里我們可以注意到，當房屋數量不超過兩間時，最多只能偷竊一間房屋，因此我們不需要考慮首尾連接的問題。但是，如果房屋數量大于二間時，就必須要考慮該限制條件了，即第一間房屋和最后一間房屋不能同時被偷竊。那么如何才能保證第一間房屋和最后一間房屋不能同時被偷竊呢？這里可以分情況來討論。

• 如果偷竊了第一間房屋，那么就不能偷竊最后一間房屋，因此可以偷竊的房屋的范圍是第一間房屋到倒數第二間房屋。
• 如果偷竊了最后一間房屋，那么就不能偷竊第一間房屋，因此可以偷竊的房屋的范圍是第二間房屋到最后一間房屋。

我們假設數組 nums 的長度為n。如果不偷竊最后一間房屋，則可以偷竊的房屋的下標是0_{n-2；如果不偷竊第一間房屋，則可以偷竊的房屋的下標是1}n-1。

接下來我們就可以采用上一題的解法，對于兩段下標范圍分別計算可以偷竊到的最高總金額，其中的最大值即為在 n 間房屋中可以偷竊到的最高總金額。

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

class Solution:    def rob(self, nums):        #求nums[start,end]范圍內可以偷竊到的最大金額        def help(start, end):            first = nums[start]            second = max(nums[start], nums[start + 1])            for i in range(start + 2, end + 1):                first, second = second, max(first + nums[i], second)            return second        length = len(nums)        #邊界條件        if length == 1:            return nums[0]        elif length == 2:            return max(nums[0], nums[1])        else:            return max(help(0, length - 2), help(1, length - 1))

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

打家劫舍III

問題描述

在上次打劫完一條街道和一圈房屋后，小偷又發現了一個新的可行竊的地區。這個地區只有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個“父”房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

示例：

輸入：[3,2,3,null,3,null,1]

     3    / /   2   3    /   /      3   1

輸出：7

解釋：小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7。

分析問題

首先我們把該問題轉化一下，該問題其實是求：對于一棵二叉樹來說，樹上的每個點都有對應的權值，并且每個點有兩種狀態（選中和不選中），在不能同時選中有父子關系的點的情況下，能選中的點的最大權值和是多少。

首先我們用f(a)來表示選擇a節點的情況下，a節點的子樹上被選擇的節點的最大權值和。g(a)表示在不選擇a節點的情況下，a節點的子樹上被選擇的節點的最大權值和。l 和 r 分別表示a的左右孩子。

小偷對于樹中的每個節點都有偷或者不偷兩種選擇，假設當前的節點是a。

• 當a被選中時，a的左右孩子都不能被選中，所以a被選中的情況下，它的子樹上被選擇的節點的最大權值和為l 和 r 不被選中的最大權值和相加，即 f(a) = g(l) + g(r)。
• 當a不被選中時，a的左右孩子可以被選中，也可以不被選中。此時 g(a) = max { f(l) , g(l) } + max{ f(r) , g(r) }。

這里我們可以使用深度優先搜索的辦法后序遍歷這棵二叉樹，就可以得到每一個節點的 f 和 g。根節點的 f和 g 的最大值就是我們要找的答案。

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

class Solution:    def __init__(self):        self.f={}        self.g={}    def dfs(self,node):        if not node:            return        self.dfs(node.left)        self.dfs(node.right)        #表示選中該節點        self.f[node]=node.val + self.g.get(node.left,0) + self.g.get(node.right,0)        #表示沒有選擇該節點        self.g[node] = max(self.f.get(node.left,0),self.g.get(node.left,0)) /                       + max(self.f.get(node.right,0),self.g.get(node.right,0))    def rob(self, root):        self.dfs(root)        return max(self.f.get(root,0),self.g.get(root,0))

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

這里我們還可以優化一下，因為無論是求 f(a) 還是 g(a)，他們的值只和 f(l) 、g(l)、f(r)和g(r)有關。所以對于每一個節點，我們只關心它的左右孩子的 f 和 g 是多少。在python中，我們可以用元組來表示，每次遞歸返回的時候，都把這個點對應的 f 和 g 返回給上一級調用。這樣我們就可以省去哈希表的空間，下面我們來看一下具體的代碼實現。

class Solution:    def dfs(self,node):        if not node:            return (0,0)        left=self.dfs(node.left)        right=self.dfs(node.right)        #表示選中該節點        selected = node.val + left[1] + right[1]        #表示沒有選擇該節點        noselected = max(left[0],left[1]) /                       + max(right[0],right[1])        return (selected,noselected)    def rob(self, root):        result=self.dfs(root)        return max(result[0],result[1])

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