[leetcode 198] House Robber

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

해결 과정

반복되는 작은 문제를 구하는 식을 구하고, 반복계산을 방지하기 위해 memoization한다.

N+1 번째가 가질 수 있는 최대값은 maxOf(N번째 결과, N-1번째 결과 + N번째 값)이다.

코드

fun rob(nums: IntArray): Int {
    if(nums.size == 0) return 0
        
    var memo = IntArray(nums.size+1)
    memo[0] = 0
    memo[1] = nums[0]
        
    for(i in 1 until nums.size) {
        memo[i+1] = maxOf(memo[i], memo[i-1] + nums[i])
   }
    return memo[nums.size]
}

배운 점

memo[i] = maxOf(memo[i-1], memo[i-2] + nums[i-1]) 과 같이 식을 구할 수도 있다. 하지만, i가 2인 경우도 초기화를 해주어야 하는데 memo[2] = maxOf(memo[1], memo[0]+nums[1]) 로 코드가 반복된다.