记忆问题 - 入室抢劫问题

Question

我有一个有效的递归解决方案，但事实证明很多子问题正在重新计算。我需要记忆方面的帮助。

所以这是问题陈述：

你是一名职业强盗，计划抢劫街道上的房屋。每栋房子都藏有一定数量的钱，唯一阻止你抢劫的限制是相邻的房子都连接了安全系统，如果相邻的两栋房子在同一天晚上被闯入，它会自动联系警方。

给定一个代表每栋房子的金额的非负整数列表，确定今晚您可以在不通知警察的情况下抢劫的最大金额。

例子：

输入：[2,7,9,3,1]输出：12解释： 抢劫房屋 1（金钱 = 2）、抢劫房屋 3（金钱 = 9）和抢劫房屋 5（金钱 = 1）。您可以抢劫的总金额 = 2 + 9 + 1 = 12.

另一个：

输入：[1,2,3,1]输出：4解释：抢夺 1 号房屋（金钱 = 1），然后抢夺 3 号房屋（金钱 = 3）。您可以抢劫的总金额 = 1 + 3 = 4.

还有另外一个

输入：[2, 1, 1, 2]输出：4解释：抢夺 1 号房屋（金钱 = 2），然后抢夺 4 号房屋（金钱 = 2）。您可以抢劫的总金额 = 2 + 2 = 4.

现在就像我说的，我有一个完美工作的递归解决方案：当我构建递归解决方案时。我没有想太多。我只是试图理解较小的子问题是什么。

option_1：我将值添加到 current 中index，然后转到index + 2

option_2：我不添加当前的值index，并且我从index + 1 最大金额=开始搜索max(option_1, option_2)

money = [1, 2, 1, 1] #Amounts that can be looted


def helper(value, index):

    if index >= len(money):

        return value

    else:
        option1 = value + money[index]
        new_index1 = index + 2

        option2 = value
        new_index2 = index + 1

        return max(helper(option1, new_index1), helper(option2, new_index2))



helper(0, 0) #Starting of at value = 0 and index = 0

这工作完美......并返回正确的值3。

然后我尝试记忆。

money = [1, 2, 1, 1]

max_dict = {}
def helper(value, index):

    if index in max_dict:
        return max_dict[index]

    elif index >= len(l1):

        return value

    else:
        option1 = value + money[index]
        new_index1 = index + 2

        option2 = value
        new_index2 = index + 1

        max_dict[index] = max(helper(option1, new_index1), helper(option2, new_index2))

        return max_dict[index]


helper(0, 0)

我只是有一个名为max_dict“存储值”的字典，每个递归调用都会检查该值是否已经存在，然后相应地抓取它并将其打印出来。

但我得到了错误的解决方案，而2不是3. 我去pythontutor.com输入了我的解决方案，但我似乎无法获得递归树及其失败的地方。

有人可以给我一个正确的记忆实现，同时保持整体结构相同吗？换句话说，我不想改变递归函数的定义

Answer 1

可以helper使用不同的value参数来调用相同的index. 因此value必须被删除（从存储的 中减去max_dict）。value一种方法是在返回之前添加，而不是更早添加：

money = [2, 1, 1, 2]

max_dict = {}
def helper(value, index):

    if index in max_dict:
        return value + max_dict[index]

    elif index >= len(money):

        return value

    else:
        option1 = money[index]
        new_index1 = index + 2

        option2 = 0
        new_index2 = index + 1

        max_dict[index] = max(helper(option1, new_index1), helper(option2, new_index2))

        return value + max_dict[index]


helper(0, 0)

@ggorlen 的回答给出了更详细的解释