ꉂ(ˊᗜˋ*)
嗨，我是wec，今天是DAY 11。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

在圍成圓形的社區內且不觸發警報的前提下(不能偷相鄰的兩間房屋)，能夠偷取的最大金額。
約束條件：
1.每間房屋中的金額都用一個非負整數表示。
2.不能同時偷取相鄰的兩間房屋。
3.數組的長度至少是 1 且不超過 100。

🔎 解題思路＆程式碼

1️⃣ 動態規劃

第1步： 如果nums是空的，直接返回 0，表示沒有房屋可搶；如果nums只有一間房，返回該房屋的金額，因為不用考慮相鄰的問題。
第2步： 利用函數prev2代表兩間之前房屋的最大收益，prev1代表上一間房屋的最大收益。遍歷每棟房屋，然後不斷更新prev1、prev2。
第3步： 由於第一間和最後一間房相鄰，不能同時搶這兩間房屋否則會觸發警報，所以我們分為兩個情況：
1.忽略第一間房屋(從第二間搶到最後一間)
2.忽略最後一間房屋(從第一間搶到倒數第二間)
第4步： 最後取兩種情況中搶劫的最大金額，return結果。
程式碼：

def rob(nums)
  return 0 if nums.empty?
  return nums[0] if nums.length == 1

  def rob_linear(houses)
    prev2, prev1 = 0, 0
    houses.each { |num| prev2, prev1 = prev1, [prev1, prev2 + num].max }
    prev1
  end

  [rob_linear(nums[1..-1]), rob_linear(nums[0...-1])].max
end

🔎 總結

時間複雜度

動態規劃： 時間複雜度為O(n)，n為房屋數量。
➡️ 看題目就知道是第一題的延伸啦～(後面還有再延伸的題目喔!)這題的解題關鍵是我們該如何處理圓形的房屋，所以將原本的形式轉換成兩個獨立的線性問題去思考，這是我覺得還蠻有趣的部份，難免都會處理到比較複雜的問題，但如何思考解題方向是很重要的第一步(๑•̀ㅂ•́)و!

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

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃中秋節放黃的柚子。
明天要說：Ruby精選刷題！Medium路跑D-4(>∀･)⌒☆