題目連結: House Robber

題目描述為: 我們現在扮演一名專業的強盜，準備要偷取街上一整排房屋內的金錢。且我們知道每間房子內的金錢是多少，而限制條件為不能對相鄰兩間房子都偷取金錢(否則會驚動警察)。要我們找出可以偷取的最大金錢總和為多少。
題目有補充說明每間房子的金錢價值均為非負整數。

例子1: input= [1,2,3,1], output= 1+3=4。
例子2: input= [2,7,9,3,1], output=2+9+1=12。

思路 1: 動態規劃法

根據題目描述，設 K>1，f(K)表示在第 K 間時可以獲取的最大金錢總和，則 f(K)=max( f(K-1), f(K-2)+v )，其中 v 表示第 K 間房子的金錢。此形式相當於依次求第 0 間房到第 K 間房所能獲取的最大金錢總和。我們將採用 day23-Climbing Stairs提到的動態規劃法來解此問題。

• 複雜度評估
  設有 N 間房子，我們需要從頭開始累加 N 次，時間複雜度為 O(N)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func rob(nums []int) int {
    
    var pre2, pre1,now int
    for _, v := range nums {
        now=max(pre2 + v, pre1)
        pre2=pre1
        pre1=now
    }
    
    return now
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

小結:

解法 1 宣告的變數 pre1,pre2 表示前兩間房子的金錢最大值，題目的補充說明每間房子的金錢價值均為非負整數讓我們不必特別處理 pre1,pre2 的初始值。
我將解法加上簡單的測試，上傳程式碼到此。

補充:

在解法 1 中我們使用了輔助凾式 func max()，Go 語言並沒有內建整數型別的 max/min 函式，只有提供浮點數型別的，但並不希望我們將整數轉型去使用，而是希望我們自行實作。