LeetCode Entry
198. House Robber
fun rob(nums: IntArray): Int {
198. House Robber medium
https://t.me/leetcode_daily_unstoppable/51
fun rob(nums: IntArray): Int {
val cache = mutableMapOf<Int, Int>()
fun dfs(pos: Int): Int {
if (pos > nums.lastIndex) return 0
return cache.getOrPut(pos) {
maxOf(nums[pos] + dfs(pos+2), dfs(pos+1))
}
}
return dfs(0)
}
Exploring each house one by one we can make a decision to rob or not to rob. The result is only depends on our current position (and all houses that are remaining to rob) and decision, so we can memoize it based on position.
We can use memoization or walk houses bottom up.
Space: O(N), Time: O(N)