代码之家 › 专栏 › 技术社区 › ababuji

记忆化问题-抢劫犯问题

memoization dynamic-programming recursion python-3.x python

ababuji · 技术社区 · 6 年前

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

下面是问题陈述:

你是一个计划沿着街道抢劫房屋的专业抢劫犯。每套房子都藏了一定数量的钱,这是唯一的限制阻止你抢劫他们的是附近的房子安全系统已连接,将自动联系警方如果两个相邻的房子在同一个晚上被闯入。

给出一个表示货币数量的非负整数列表在每栋房子里,确定你能抢劫的最大金额今晚没有报警。

实例:

输入: [2,7,9,3,1] 输出: 12 说明:Rob House 1(货币=2) Rob House 3(金钱=9)和Rob House 5(金钱=1)。你可以抢劫的总金额= 2 + 9 + 1 = 12 .

另一个:

输入: [1,2,3,1] 输出: 4 说明:Rob House 1(货币=1)和然后Rob House 3(钱=3)。你可以抢劫的总金额= 1 + 3 = 4 .

另一个

输入: [2, 1, 1, 2] 输出: 四 说明:Rob House 1(货币=2)和然后Rob House 4(钱=2)。你可以抢劫的总金额= 2 + 2 = 4 .

现在就像我说的,我有一个完美的递归解决方案:当我构建一个递归解决方案时。我不想太多。我只是试着理解较小的子问题是什么。

option_1 :我在当前值中添加值 index 然后去 index + 2

option_2 :我不在当前值中添加值 指数 ,我从开始搜索 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 而不是 三 . 我去了 pythontutor.com 并输入了我的解决方案,但我似乎无法得到递归树以及它失败的地方。

有人能在保持整体结构不变的情况下给我一个正确的记忆实现吗?换句话说,我不希望递归函数定义更改

2 回复 | 直到 6 年前

Michael Butscher 6 年前

这个 helper 可以用不同的 value 相同的参数 index . 所以 价值 必须删除(从存储的 max_dict )一种方法是添加 价值 在返回之前,而不是更早:

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的答案给出了更详细的解释

ggorlen Hoàng Huy Khánh 6 年前

你的记忆方法不起作用,因为当你达到某个指数时 i ,如果您已经计算了 我 ,您的算法无法考虑可能存在 更好的 结果是在阵列的左侧抢劫了一组更为理想的房子。

解决这个难题的办法是避免跑动 value (你抢的钱)通过父母对孩子的递归调用向下。其思想是计算子问题的结果 任何输入 从祖先节点,然后在返回调用堆栈的过程中从较小的节点构建较大的解决方案。

索引的记忆化 我 然后会工作,因为给定的索引 我 总是有一组独特的子问题,其解决方案不会被数组左侧祖先的选择所破坏。这就保留了DP工作所必需的最佳子结构。

此外,我建议避免使用全局变量,以便将数据直接传递到函数中。

def maximize_robberies(houses, memo, i=0):
    if i in memo:
        return memo[i]
    elif i >= len(houses):
        return 0

    memo[i] = max(
        houses[i] + maximize_robberies(houses, memo, i + 2),
        maximize_robberies(houses, memo, i + 1)
    )
    return memo[i]


print(maximize_robberies([1, 2, 1, 1], {}))

Try it!