198.house-robber.md

198. House Robber

For the house of i we have two choises:

1. Rob the i-2 and i house, or
2. Rob i-1 house and can't rob i house.

Then we find the maximum between the two choices.

Top-Down DP

fun rob(nums: IntArray): Int {
    val memo = IntArray(nums.size) { -1 }
    return rob(nums, nums.size - 1, memo)
}

private fun rob(nums: IntArray, i: Int, memo: IntArray): Int {
    if (i == 0) return nums[0]
    if (i == 1) return maxOf(nums[0], nums[1])
    if (memo[i] != -1) return memo[i]
    memo[i] = maxOf(
        nums[i] + topDown(nums, i - 2, memo),
        topDown(nums, i - 1, memo)
    )
    return memo[i]
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Bottom-Up DP

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

• Time Complexity: O(n)
• Space Complexity: O(n)

Bottom-Up DP (Space Optimization)

fun rob(nums: IntArray): Int {
    val n = nums.size
    if (n == 1) return nums[0]
    if (n == 2) return maxOf(nums[0], nums[1])
    var result = 0
    var n2 = nums[0]
    var n1 = maxOf(nums[0], nums[1])
    for (i in 2 until n) {
        result = maxOf(
            n2 + nums[i],
            n1
        )
        n2 = n1
        n1 = result
    }
    return result
}

• Time Complexity: O(n)
• Space Complexity: O(1)