偷金幣

有x個房間(int array count)，黃金的價值為整數陣列的值，相鄰的房子(item)不能連續被小偷盜取，求得最高盜取獲利。

/*
Input:
 House = [3, 5, 2, 10]
 
Output:
 15
*/

//演算
class Solution {
    
    func GetGold(houses: [Int]) -> Int {
        var memo: [Int] = Array(0...houses.count - 1)
        for i:Int in memo {
            memo[i] = -1
        }
        return GetMemo(id: 0, memo: &memo, houses: houses)
    }
    
    func GetMemo(id: Int, memo: inout [Int], houses: [Int]) -> Int {
        if (id >= memo.count) {
            return 0
        }
        if (memo[id] != -1) {
            return memo[id]
        }
        let selectFirstElement: Int = houses[id] + GetMemo(id: id + 2, memo: &memo, houses: houses)
        let unselectFirstElement: Int = GetMemo(id: id + 1, memo: &memo, houses: houses)
        
        memo[id] = max(selectFirstElement, unselectFirstElement)
        return memo[id]
    }
}

//執行測試
var solution = Solution()
print(solution.GetGold(houses: [3, 5, 2, 10]))
print(solution.GetGold(houses: [8, 5, 4, 10, 9]))
print(solution.GetGold(houses: [5, 4, 9]))

//輸出
15
21
14