Leetcode House Robber custom与自定义测试案例

Question

我正在研究198.屋贼 LeetCode问题：

你是一个职业抢劫犯，打算抢劫街道上的房屋。每间房子都藏着一定数量的钱，阻止你抢劫每栋房子的唯一限制是相邻的房子都有安全系统连接，如果相邻的两栋房子在同一个晚上被闯入，会自动联系警察。 给定一个整数数组nums，表示每所房子的钱数，返回你今晚可以抢劫的最大金额，没有通知警方。 示例1： 投入: nums = 1,2,3,1产出:4 解释：抢劫房屋1(货币= 1)，然后抢劫房屋3(货币= 3)。 你可以抢劫的总数=1+3= 4。 示例2： 投入: nums = 2,7,9,3,1产出: 12 解释：抢劫房屋1(货币= 2)，抢劫房屋3(货币= 9)，抢劫房屋5(货币= 1)。 你可以抢劫的总数=2+9+1= 12。

我的代码

class Solution:
    def rob(self, nums, n=0, memo={}):
        if n in memo:
            return memo[n]
        
        if n == len(nums) - 1:
            return nums[n]
        if n > len(nums) - 1:
            return 0
        
        f = nums[n] + self.rob(nums, n + 2)
        s = nums[n + 1] + self.rob(nums, n + 3)
        
        memo[n] = max(f, s)

        return max(f, s)

当我单击submit按钮时，输入：[2,7,9,3,1]会失败。但是，当我把它作为一个自定义测试用例运行时，它似乎起作用了：

​

​

Answer 1

问题在于memo参数。

由于它是定义的(memo={})，它永远不会在测试用例之间重置，因此它将携带与当前测试用例无关的值。

与其他语言不同的是，参数的默认值仅在函数定义时计算，而不是在执行时计算。

因此，请确保将memo定义为函数中的局部变量，而不是参数。

您可以在rob中作为嵌套函数创建递归函数，以便在递归期间访问相同的memo实例。

因此，将您的代码更改为：

def rob(self, nums):
    memo = {}  # define here so it gets reset at every call
    
    def recur(n):  # recursive function with access to memo
        if n in memo:
            return memo[n]

        if n == len(nums) - 1:
            return nums[n]
        if n > len(nums) - 1:
            return 0

        f = nums[n] + recur(n + 2)
        s = nums[n + 1] + recur(n + 3)

        memo[n] = max(f, s)

        return max(f, s)
    
    return recur(0)

Answer 2

下面是我不断更新元素并根据规则找到最大和的代码：

class Solution:
    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]

        elif len(nums) == 2:
            return max(nums[0], nums[1])

        else:
            robFirst = nums[0]
            robSecond = max(nums[0], nums[1])

            for i in range(2, len(nums)):
                current = max(robSecond, robFirst + nums[i])

                robFirst = robSecond
                robSecond = current

        return robSecond