Skip to main content

198. House Robber

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

Python​

(First Try)​

class Solution:
    def rob(self, nums: List[int]) -> int:
        total_1 = 0
        total_2 = 0

        for index, num in enumerate(nums):
            if index % 2 == 0:
                total_1 = max(total_1 + num, total_2)
            else:
                total_2 = max(total_2 + num, total_1)
        return max(total_1, total_2)

Top-down DP​

from functools import cache


class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def dp(i):
            if i == 0:
                return nums[0]
            if i == 1:
                return max(nums[0], nums[1])
            return max(dp(i-1), dp(i-2)+nums[i])

        return dp(len(nums)-1)

Bottom-up DP​

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return nums[0]

        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])

        return dp[-1]

Bottom-up DP​

  • 降維打擊
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        t1, t2 = 0, 0

        for num in nums:
            temp = t1
            t1 = max(num+t2, t1)
            t2 = temp

        return t1

Go​

Bottom-Up DP​

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }

    dp := make([]int, len(nums))

    dp[0] = nums[0]
    if (nums[0] > nums[1]) {
        dp[1] = nums[0]
    } else {
        dp[1] = nums[1]
    }

    for i:=2; i<len(nums); i++ {
        taken := dp[i-2]+nums[i]
        skip := dp[i-1]

        if (taken > skip) {
            dp[i] = taken
        } else {
            dp[i] = skip
        }

    }
    return dp[len(dp)-1]
}

JS​


// top-down
var rob = function(nums) {
    if (nums.length === 1) return nums[0];

    function dp(i) {
        if (i === 0) return nums[0];
        else if (i === 1) return Math.max(nums[0], nums[1]);
        return Math.max(nums[i] + dp(i - 2), dp(i - 1));
    }
    return dp(nums.length - 1);
};

// bottom-up
var rob = function(nums) {
  if (nums.length === 1) return nums[0];

  let prev = nums[0];
  let curr = Math.max(nums[0], nums[1]);

  for (let i = 2; i < nums.length; i++) {
    let tmp = curr;
    curr = Math.max(nums[i] + prev, curr);
    prev = tmp;
  }

  return curr;
};

/**
 *
 * base case:
 * dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
 *
 * transition fn:
 * dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
 */