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

打家劫舍I

問題描述

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

示例：

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

輸出：4

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

分析問題

首先，我們先將問題簡化處理。假設(shè)目前只有一間房屋，則偷竊該房屋，此時就是偷竊到的最高總金額。如果只有兩間房屋，因?yàn)榇藭r兩間房屋相鄰，只能偷竊其中的一間房屋，可以選擇其中金額較高的房屋進(jìn)行偷竊，就是可以偷竊到的最高總金額。如果房屋的數(shù)量大于兩間，假設(shè)小偷此時處于第k（k>2）間房屋，那么他有兩個選擇。

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

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

我們用 dp[i] 來表示前 i 間房屋能偷竊到的最高總金額，經(jīng)過前面的分析，可以知道其狀態(tài)轉(zhuǎn)移方程為：

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

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

下面我們來看一下代碼的實(shí)現(xiàn)。

class Solution:    def rob(self, nums):        #如果數(shù)組為空，則直接返回0        if not nums:            return 0                length = len(nums)        #如果房屋數(shù)量等于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]

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

通過觀察，我們發(fā)現(xiàn)dp[i] 只和 dp[i-2] 和 dp[i-1]有關(guān)，即只和該房屋的前兩間房屋的最高總金額相關(guān)，所以我們可以使用滾動數(shù)組，在每個時刻只需要存儲前兩間房屋的最高總金額即可，從而降低空間復(fù)雜度。我們來看一下代碼的實(shí)現(xiàn)。

class Solution:    def rob(self, nums):        #如果數(shù)組為空，則直接返回0        if not nums:            return 0        length = len(nums)        #如果房屋數(shù)量等于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

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

打家劫舍II

問題描述

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

示例：

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

輸出：3

解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?/p>

分析問題

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

我們也可以和上一道題的思路一樣，采用動態(tài)規(guī)劃的方法來求解。首先先將問題簡單化，假設(shè)此時只有一間房屋，則偷竊該房屋，此時就是偷竊到的最高總金額。如果只有兩間房屋，因?yàn)榇藭r兩間房屋相鄰，只能偷竊其中的一間房屋，可以選擇其中金額較高的房屋進(jìn)行偷竊，就是可以偷竊到的最高總金額。

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

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

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

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

下面我們來看一下代碼的實(shí)現(xiàn)。

class Solution:    def rob(self, nums):        #求nums[start,end]范圍內(nèi)可以偷竊到的最大金額        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))

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

打家劫舍III

問題描述

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

示例：

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

     3    / /   2   3    /   /      3   1

輸出：7

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

分析問題

首先我們把該問題轉(zhuǎn)化一下，該問題其實(shí)是求：對于一棵二叉樹來說，樹上的每個點(diǎn)都有對應(yīng)的權(quán)值，并且每個點(diǎn)有兩種狀態(tài)（選中和不選中），在不能同時選中有父子關(guān)系的點(diǎn)的情況下，能選中的點(diǎn)的最大權(quán)值和是多少。

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

小偷對于樹中的每個節(jié)點(diǎn)都有偷或者不偷兩種選擇，假設(shè)當(dāng)前的節(jié)點(diǎn)是a。

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

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

下面我們來看一下代碼的實(shí)現(xiàn)。

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)        #表示選中該節(jié)點(diǎn)        self.f[node]=node.val + self.g.get(node.left,0) + self.g.get(node.right,0)        #表示沒有選擇該節(jié)點(diǎn)        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))

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

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

class Solution:    def dfs(self,node):        if not node:            return (0,0)        left=self.dfs(node.left)        right=self.dfs(node.right)        #表示選中該節(jié)點(diǎn)        selected = node.val + left[1] + right[1]        #表示沒有選擇該節(jié)點(diǎn)        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])

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