[LeetCode] 198. House Robber(Kotlin)

0

LeetCode

목록 보기
14/58
post-thumbnail

[LeetCode] 198. House Robber(Kotlin)

풀이

class Solution {
    // money[i]: i번째 집에서 털 수 있는 돈
    private lateinit var money: List<Int>
    // memoization
    private lateinit var memo: MutableList<Int>

    fun rob(nums: IntArray): Int{
        money = nums.toList()
        memo = MutableList<Int>(nums.size){-1}
        return getMaxMoney(0)
    }

    private fun getMaxMoney(curHouse:Int): Int{
        if(curHouse >= money.size) return 0

        if(memo[curHouse] != -1) return memo[curHouse]
        var maxMoney = 0
        maxMoney = max(maxMoney, 0 + getMaxMoney(curHouse+1))
        maxMoney = max(maxMoney, money[curHouse] + getMaxMoney(curHouse+2))

        memo[curHouse] = maxMoney
        return maxMoney
    }
}
profile
Be able to be vulnerable, in search of truth

0개의 댓글