198. House Robber

題目敘述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

題目翻譯

假設你是一個專業的搶匪，今天的目標是要搶劫一條街上的房子。每個房子都有防盜系統，其條件是當同一晚相鄰的兩間房子都被闖入時會報警。給定一個陣列 nums，每個索引代表每間房子最多可以搶到多少錢。計算出最多可以搶到多少錢。

解法解析

其解法可以分為三種：Recursion、Iteration 和空間優化後的 Iteration。因為搶了第一間房子的話就不能搶第二間，解答是依據每次的選擇堆疊而成的。所以是典型的 Dynamic programming 問題。

主要的關鍵邏輯就是，每次選擇房子的時候是拿後面兩個來比較。目前在 i = 0 的位置，因為搶了 i = 0 的房子的話，就不能搶 i = 1 的房子。這樣的話至少 i[0] + i[2] >= i[1]才比較有效益，不然的話就是選擇i[1]` 的房子了。每次的選擇都是基於此條件，最後堆疊出最後的答案。

解法範例

Go

Recursion with Memoization

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    var memo map[int]int = make(map[int]int, len(nums))
    return robFrom(memo, 0, nums)
}

func robFrom(memo map[int]int, i int, nums []int) int {
    if i >= len(nums) {
        return 0
    }

    if _, ok := memo[i]; ok {
        return memo[i]
    }
    if robFrom(memo, i+1, nums) > robFrom(memo, i+2, nums)+nums[i] {
        memo[i] = robFrom(memo, i+1, nums)
    } else {
        memo[i] = robFrom(memo, i+2, nums) + nums[i]
    }
    return memo[i]
}

Dynamic Programming

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

    var N int = len(nums)
    var maxRobbedAmount []int = make([]int, N+1)

    maxRobbedAmount[N], maxRobbedAmount[N-1] = 0, nums[N-1]
    for i := N - 2; i >= 0; i-- {
        if maxRobbedAmount[i+1] > maxRobbedAmount[i+2]+nums[i] {
            maxRobbedAmount[i] = maxRobbedAmount[i+1]
        } else {
            maxRobbedAmount[i] = maxRobbedAmount[i+2] + nums[i]
        }
    }
    return maxRobbedAmount[0]
}

Optimized Dynamic Programming

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    var N int = len(nums)
    var robNext, robNextPlusOne int = nums[N-1], 0
    for i := N - 2; i >= 0; i-- {
        if robNext > robNextPlusOne+nums[i] {
            robNext, robNextPlusOne = robNext, robNext
        } else {
            robNext, robNextPlusOne = robNextPlusOne+nums[i], robNext
        }
    }
    return robNext
}

JavaScript

Recursion with Memoization

/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = function (nums) {
    const memo = {};

    const robFrom = (i, rob_nums) => {
        if (i >= rob_nums.length) {
            return 0;
        }
        if (i in memo) {
            return memo[i];
        }
        const ans = Math.max(rob_nums[i] + robFrom(i + 2, rob_nums), robFrom(i + 1, rob_nums));
        memo[i] = ans;
        return ans;
    };

    return robFrom(0, nums);
};

Dynamic Programming

/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = function (nums) {
    if (!nums) {
        return 0;
    }

    const N = nums.length;
    const maxRobbedAmount = new Array(N + 1).fill(0);
    maxRobbedAmount[N] = 0;
    maxRobbedAmount[N - 1] = nums[N - 1];

    for (let i = N - 2; i >= 0; i--) {
        maxRobbedAmount[i] = Math.max(nums[i] + maxRobbedAmount[i + 2], maxRobbedAmount[i + 1]);
    }
    return maxRobbedAmount[0];
};

Optimized Dynamic Programming

/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = function (nums) {
    if (!nums) {
        return 0;
    }

    const N = nums.length;
    let robNextPlusOne = 0,
        robNext = nums[N - 1];

    for (let i = N - 2; i >= 0; i--) {
        const current = Math.max(robNext, robNextPlusOne + nums[i]);
        robNextPlusOne = robNext;
        robNext = current;
    }
    return robNext;
};

Kotlin

Recursion with Memoization

class Solution {
    protected lateinit var memo: MutableMap<Int, Int>

    fun rob(nums: IntArray): Int {
        memo = mutableMapOf()
        return robFrom(0, nums)
    }

    fun robFrom(i: Int, nums: IntArray): Int {
        if (i >= nums.size) return 0
        if (memo[i] != null) return memo[i]!!
        val res = Math.max(robFrom(i + 1, nums), nums[i] + robFrom(i + 2, nums))
        memo[i] = res
        return res
    }
}

Dynamic Programming

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 0) {
            return 0
        }

        val N: Int = nums.size
        var maxRobbedAmount: IntArray = IntArray(N + 1)
        maxRobbedAmount[N] = 0
        maxRobbedAmount[N - 1] = nums[N - 1]
        for (i in N - 2 downTo 0) {
            maxRobbedAmount[i] = Math.max(maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i])
        }
        return maxRobbedAmount[0]
    }
}

Optimized Dynamic Programming

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 0) {
            return 0
        }

        val N: Int = nums.size
        var robNext: Int = nums[N - 1]
        var robNextPlusOne: Int = 0
        for (i in N - 2 downTo 0) {
            val current: Int = Math.max(robNext, robNextPlusOne + nums[i])
            robNextPlusOne = robNext
            robNext = current
        }
        return robNext
    }
}

PHP

Recursion with Memoization

class Solution
{
    private $memo = [];

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums)
    {
        return $this->robFrom(0, $nums);
    }

    function robFrom($i, $nums)
    {
        if ($i >= count($nums)) {
            return 0;
        }
        if (isset($this->memo[$i])) {
            return $this->memo[$i];
        }
        $ans = max($this->robFrom($i + 1, $nums), $this->robFrom($i + 2, $nums) + $nums[$i]);
        $this->memo[$i] = $ans;
        return $ans;
    }
}

Dynamic Programming

class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums)
    {
        if (empty($nums)) {
            return 0;
        }
        $N = count($nums);
        $maxRobbedAmount = array_fill(0, $N + 1, 0);
        $maxRobbedAmount[$N] = 0;
        $maxRobbedAmount[$N - 1] = $nums[$N - 1];
        for ($i = $N - 2; $i >= 0; $i--) {
            $maxRobbedAmount[$i] = max($maxRobbedAmount[$i + 1], $maxRobbedAmount[$i + 2] + $nums[$i]);
        }
        return $maxRobbedAmount[0];
    }
}

Optimized Dynamic Programming

class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums)
    {
        if (empty($nums)) {
            return 0;
        }
        $N = count($nums);
        $robNext = $nums[$N - 1];
        $robNextPlusOne = 0;
        for ($i = $N - 2; $i >= 0; $i--) {
            $current = max($robNext, $robNextPlusOne + $nums[$i]);
            $robNextPlusOne = $robNext;
            $robNext = $current;
        }
        return $robNext;
    }
}

Python

Recursion with Memoization

class Solution:
    def __init__(self) -> None:
        self.memo: dict[int, int] = {}

    def rob(self, nums: list[int]) -> int:
        self.memo = {}
        return self.robFrom(0, nums)

    def robFrom(self, i: int, nums: list[int]) -> int:
        # No more houses left to examine.
        if i >= len(nums):
            return 0

        # Return cached value.
        if i in self.memo:
            return self.memo[i]

        # Recursive relation evaluation to get the optimal answer.
        ans: int = max(self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i])

        # Cache for future use.
        self.memo[i] = ans
        return ans

Dynamic Programming

class Solution:
    def rob(self, nums: list[int]) -> int:
        # Special handling for empty case.
        if not nums:
            return 0

        N: int = len(nums)
        maxRobbedAmount: list[int | None] = [None for _ in range(N + 1)]

        # Base case initialization.
        maxRobbedAmount[N], maxRobbedAmount[N - 1] = 0, nums[N - 1]

        # DP table calculations.
        for i in range(N - 2, -1, -1):

            # Same as recursive solution.
            maxRobbedAmount[i] = max(
                maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i]
            )

        return maxRobbedAmount[0]

Optimized Dynamic Programming

class Solution:
    def rob(self, nums: list[int]) -> int:

        # Special handling for empty case.
        if not nums:
            return 0

        N: int = len(nums)

        rob_next_plus_one: int = 0
        rob_next: int = nums[N - 1]

        # DP table calculations.
        for i in range(N - 2, -1, -1):

            # Same as recursive solution.
            current: int = max(rob_next, rob_next_plus_one + nums[i])

            # Update the variables
            rob_next_plus_one = rob_next
            rob_next = current

        return rob_next

Rust

Swift

Recursion with Memoization

class Solution {

    var memo: [Int: Int] = [Int: Int]()

    func rob(_ nums: [Int]) -> Int {
        return robFrom(0, nums: nums)
    }

    func robFrom(_ i: Int, nums: [Int]) -> Int {
        if i >= nums.count {
            return 0
        }
        if let memoized: Int = memo[i] {
            return memoized
        }
        let result: Int = max(robFrom(i + 1, nums: nums), nums[i] + robFrom(i + 2, nums: nums))
        memo[i] = result
        return result
    }
}

Dynamic Programming

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }

        let N: Int = nums.count
        var maxRobbedAmount: [Int] = Array(repeating: 0, count: N + 1)
        maxRobbedAmount[N] = 0
        maxRobbedAmount[N - 1] = nums[N - 1]

        for i: Int in (0..<N - 1).reversed() {
            maxRobbedAmount[i] = max(maxRobbedAmount[i + 1], nums[i] + maxRobbedAmount[i + 2])
        }

        return maxRobbedAmount[0]
    }
}

Optimized Dynamic Programming

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }

        let N: Int = nums.count
        var robNextPlusOne: Int = 0
        var robNext: Int = nums[N - 1]

        for i: Int in (0..<N - 1).reversed() {
            let current: Int = max(robNext, nums[i] + robNextPlusOne)
            robNextPlusOne = robNext
            robNext = current
        }
        return robNext
    }
}