<input id="0qass"><u id="0qass"></u></input>
  • <input id="0qass"><u id="0qass"></u></input>
  • <menu id="0qass"><u id="0qass"></u></menu>

    打家劫舍(動態規劃)

    算法 同時被 2 個專欄收錄
    6 篇文章 0 訂閱
    5 篇文章 0 訂閱

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

    考慮所有可能的搶劫方案過于困難。一個自然而然的想法是首先從最簡單的情況開始。記:

    f(k) = 從前 k 個房屋中能搶劫到的最大數額,A_iA i = 第 i 個房屋的錢數。

    首先看 n = 1 的情況,顯然 f(1) = A_1A 1 。

    再看 n = 2,f(2) = max(A_1A 1 , A_2A 2 )。

    對于 n = 3,有兩個選項:

    搶第三個房子,將數額與第一個房子相加。

    不搶第三個房子,保持現有最大數額。

    顯然,你想選擇數額更大的選項。于是,可以總結出公式:

    f(k) = max(f(k – 2) + A_kA k , f(k – 1))

    我們選擇 f(–1) = f(0) = 0 為初始情況,這將極大地簡化代碼。

    答案為 f(n)??梢杂靡粋€數組來存儲并計算結果。不過由于每一步你只需要前兩個最大值,兩個變量就足夠用了。

    class Solution:
        def rob(self, nums: List[int]) -> int:
            n = len(nums)
            if n == 0:
                return 0
            pre = cur = 0
            for c in nums:
                pre, cur = cur, max(pre + c, cur)
            return cur
    

    打家劫舍(Ⅱ)
    你是一個專業的小偷,計劃偷竊沿街的房屋,每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈,這意味著第一個房屋和最后一個房屋是緊挨著的。同時,相鄰的房屋裝有相互連通的防盜系統,如果兩間相鄰的房屋在同一晚上被小偷闖入,系統會自動報警。

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

    環狀排列意味著第一個房子和最后一個房子中只能選擇一個偷竊,因此可以把此環狀排列房間問題約化為兩個單排排列房間子問題:
    在不偷竊第一個房子的情況下(即 nums[1:]nums[1:]),最大金額是 p_1p1;在不偷竊最后一個房子的情況下(即 nums[:n-1]nums[:n?1]),最大金額是 p_2p 2 。綜合偷竊最大金額: 為以上兩種情況的較大值,即 max(p1,p2)max(p1,p2) 。

    class Solution:
        def rob(self, nums: [int]) -> int:
            def my_rob(nums):
                cur, pre = 0, 0
                for num in nums:
                    cur, pre = max(pre + num, cur), cur
                return cur
            return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0]
    
    • 0
      點贊
    • 0
      評論
    • 0
      收藏
    • 打賞
      打賞
    • 掃一掃,分享海報

    參與評論 您還未登錄,請先 登錄 后發表或查看評論
    ??2022 CSDN 皮膚主題:大白 設計師:CSDN官方博客 返回首頁

    打賞作者

    小饅頭的yy

    你的鼓勵將是我創作的最大動力

    ¥2 ¥4 ¥6 ¥10 ¥20
    輸入1-500的整數
    余額支付 (余額:-- )
    掃碼支付
    掃碼支付:¥2
    獲取中
    掃碼支付

    您的余額不足,請更換掃碼支付或充值

    打賞作者

    實付
    使用余額支付
    點擊重新獲取
    掃碼支付
    錢包余額 0

    抵扣說明:

    1.余額是錢包充值的虛擬貨幣,按照1:1的比例進行支付金額的抵扣。
    2.余額無法直接購買下載,可以購買VIP、C幣套餐、付費專欄及課程。

    余額充值
    多乐彩