天天看點

<LeetCode天梯>Day040 打家劫舍(動态規劃) | 初級算法 | Python

以下為我的天梯積分規則:

每日至少一題:一題積分+10分

若多做了一題(或多一種方法解答),則當日積分+20分(+10+10)

若做了三道以上,則從第三題開始算+20分(如:做了三道題則積分-10+10+20=40;做了四道題則積分–10+10+20+20=60)

初始分為100分

若差一天沒做題,則扣積分-10分(周六、周日除外注:休息)

堅持!!!

初級算法

刷題目錄

動态規劃

<LeetCode天梯>Day040 打家劫舍(動态規劃) | 初級算法 | Python
<LeetCode天梯>Day040 打家劫舍(動态規劃) | 初級算法 | Python

題幹

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

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

示例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 。

分析:

目的是為了獲得最高金額,但是不能連續偷兩家,是以就兩兩進行選擇,選擇最大的,然後再跳過一家,在下面兩家的中選取最大,這樣,到最後就能獲得最大的利益。

class Solution:
    def rob(self, nums: List[int]) -> int:
        a=b=0
        for x in nums:
            a, b = max(a, b), a + x
        return max(a, b)      
<LeetCode天梯>Day040 打家劫舍(動态規劃) | 初級算法 | Python