LeetCode-打家劫舍-動态規劃

1、打家劫舍-

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]

輸出: 4

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

示例 2:

輸入: [2,7,9,3,1]

輸出: 12

解釋: 偷竊 1 号房屋 (金額 = 2), 偷竊 3 号房屋 (金額 = 9)，接着偷竊 5 号房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12 。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/house-robber/

解析：

f[i]表示0-i的最大金額，f[i] = max(f[i - k] + nums[i]，f[i])，k為間隔數量

def rob1(nums):
    if not nums:
        return 0
    n = len(nums)
    f = list(nums)
    f[0] = nums[0]
    for i in range(n):
        for k in range(2, i + 1):
            if i >= k and f[i] < f[i - k] + nums[i]:
                f[i] = f[i - k] + nums[i]
    return max(f)
           

2、打家劫舍 II

同上，但是有差別：這個地方所有的房屋都圍成一圈，這意味着第一個房屋和最後一個房屋是緊挨着的。

示例 1:

輸入: [2,3,2]

輸出: 3

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

示例 2:

輸入: [1,2,3,1]

輸出: 4

解釋: 你可以先偷竊 1 号房屋（金額 = 1），然後偷竊 3 号房屋（金額 = 3）。偷竊到的最高金額 = 1 + 3 = 4 。

來源：力扣（LeetCode）

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

解析：

        環狀排列意味着第一個房子和最後一個房子中隻能選擇一個偷竊，是以可以把此環狀排列房間問題約化為兩個單排排列房間子問題：

        1、在不偷竊第一個房子的情況下（即 nums[1:]nums[1:]），最大金額是 p1

        2、在不偷竊最後一個房子的情況下（即 nums[:n-1]nums[:n−1]），最大金額是 p2

        綜合偷竊最大金額： 為以上兩種情況的較大值，即 max(p1,p2) 。

def rob2(nums):
        if not nums:
            return 0

        n = len(nums)
        f = list(nums)

        for i in range(1, n):
            for k in range(2, i + 1):
                if i - k >= 1 and f[i] < f[i - k] + nums[i]:
                    f[i] = f[i - k] + nums[i]

        f2 = list(nums)
        for i in range(n-1):
            for k in range(2, i + 1):
                if i - k >= 0 and f2[i] < f2[i - k] + nums[i]:
                    f2[i] = f2[i - k] + nums[i]

        return max(f + f2)
           

3、打家劫舍 III

本題不是動态規劃，樹的DFS

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

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

示例 1:

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

     3

    / \

   2   3

    \   \ 

     3   1

輸出: 7 

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

示例 2:

輸入: [3,4,5,1,3,null,1]

     3

    / \

   4   5

  / \   \ 

 1   3   1

輸出: 9

解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/house-robber-iii/

def rob(root):
    # res1為不包括根節點的最大值，res2為包括根節點的最大值
    def dfs(root):
        if not root:
            return 0, 0

        left1, left2 = dfs(root.left)
        right1, right2 = dfs(root.right)
        res1 = max(left1, left2) + max(right1, right2)
        res2 = left1 + right1 + root.val
        return res1, res2

    return max(dfs(root))