House Robber

문제

https://leetcode.com/problems/house-robber/description/

입력

1 <= nums.length <= 100 // 집 개수
0 <= nums[i] <= 400 // 가지고 있는 재산

결과

ans: Int = 훔칠 수 있는 최대 금액

해석

인접 집을 건드리면 안되기 때문에 현재 집을 털기 위해서는 이전 집을 털지 않아야함

현재 위치가 i라 할때 필요한 정보는 i-1과 i-2

코드

class Solution {    
    func rob(_ nums: [Int]) -> Int {
        let n = nums.count
        var cache: [Int] = [Int](repeating: 0, count:n)
        if n == 1 {
            return nums[0]
        }
        
        cache[0] = nums[0]
        cache[1] = max(cache[0],nums[1])

        for i in 2..<n {
            cache[i] = max(cache[i-1], cache[i-2] + nums[i])
        }

        return cache[n-1]
    }
}