٩(◕‿◕｡)۶
嗨，我是wec，今天是DAY 10。

🔎 題目難度與描述
難度：MEDIUM
題目描述：
給定一個代表房屋的非負整數數組，每個房子裡有一定的金錢，搶匪不能搶劫相鄰的兩間房子，求在不觸發警報的情況下能搶劫的最大金額。

🔎 解題思路＆程式碼

1️⃣ 動態規劃

第1步： 先做初始化，用兩個變量來記住搶劫過程中的兩個數字，prev2代表兩間房之前能拿到的最多錢，prev1：上一間房子能拿到的最多錢。
第2步： 決定是搶這間房子（加上prev2）還是只保持前一間房搶到的錢（prev1），透過不斷更新這兩個數字，讓每次迭代後都保持最新的狀況。
第3步： 直到看完所有房子，prev1就是能搶到的最多錢。
程式碼：

def rob(nums)
  prev2, prev1 = 0, 0
  
  nums.each do |num|
    prev2, prev1 = prev1, [prev1, prev2 + num].max
  end
  
  prev1
end

🔎 總結

時間複雜度

動態規劃： 時間複雜度為O(n)
➡️ 除了時間複雜度之外，因為只使用了兩個變量來記錄狀態，因此空間複雜度是優秀的O(1)，節省了內存，很適合用來處理數據較為複雜大量的情況！這題還有延伸，像是House Robber II，也可以透過更改一些片段，就可以適應不同的要求跟情況！

那麽，以上就是今天的內容嚕！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃超市買的蔥肉餅。
明天要說：Ruby精選刷題！Medium路跑D-4(>∀･)⌒☆