【Leetcode 筆記】198. House Robber

題目解釋

你是一名職業搶匪，計劃搶劫街上的房屋。

每棟房子都藏有一定數量的錢，唯一阻止你搶劫的限制是相鄰的房子都有安全系統連接，
如果相鄰的兩棟房子在同一天晚上被闖入，它會自動聯繫警方。

給定一個表示每棟房子的金額的整數陣列 nums，回傳今晚您可以在不報警的情況下搶劫的最大金額。

範例

• 輸入: nums = [1, 2, 3, 1]
• 輸出: 4

搶劫 1 號房屋（金錢 = 1），然後搶劫 3 號房屋（金錢 = 3）。
您可以搶劫的總金額 = 1 + 3 = 4。

最佳解法

1. 先偷看搶 1 位 + 3 位 or 2 位 哪個比較多錢
2. rob1 前進一格，eg. [原 rob1, 新 rob1, 新 rob2, n, ...]
3. rob2 更新為目前的最高值

程式碼

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for n in nums:
            local_max = max(rob1 + n, rob2)
            rob1 = rob2
            rob2 = local_max

        return rob2

時間複雜度

O(n)，n 是 nums 的長度。

空間複雜度

O(1)。

結語

這下就知道學會 DP 的話，找工作的方向又變廣了吧 (x

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26