leetcode-0198 打家劫舍

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

对于一个数组，

第 n 间房屋的金额为 M(n), 最大获利 F(n)

F(n) = F(n-2) + M(n)

每间屋子里的金额为非负整数，所以整晚的最大获利的最后一间屋子，要么是 F(n)，要么是 F(n-1)

最大获利 = max(F(n), F(n-1))

自底向上来计算：

一间屋子，最大获利两间屋子，最大获利 ... n 间屋子，最大获利

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        elif len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[1], nums[0])
        memo = {}
        memo[0] = nums[0]
        memo[1] = max(nums[1], nums[0])
        for i in range(2, len(nums)):
            memo[i] = max(nums[i] + memo[i-2], memo[i-1])
        return max(memo[i], memo[i-1])

只需要保留前一个位置的最大值和当前位置的最大值。总的最大值就在这两个中取。

改成空间复杂度为 O(1) 的版本：

class Solution:
    def rob(self, nums: List[int]) -> int:
        pre_max = 0
        cur_max = 0
        for x in nums:
            new_max = max(pre_max+x, cur_max)
            pre_max = cur_max
            cur_max = new_max
        return max(cur_max, pre_max)

meishaoming / blog

leetcode-0198 打家劫舍 #82