备忘录算法存在问题-打家劫舍问题

Question

我有一个递归解决方案，但是发现许多子问题被重复计算了。我需要MEMOIZATION的帮助。

这是问题陈述： 你是一名专业的抢劫犯，打算在街道上抢劫房屋。每个房子都藏有一定数量的钱，唯一限制你抢劫他们的是相邻的房屋有连接的安全系统，如果在同一晚上闯入两个相邻的房屋，它会自动联系警察。 给定一个表示每个房屋钱数的非负整数列表，确定今晚你可以在不警告警方的情况下抢到的最大金额。

示例： 输入: [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。

现在，像我说的，我有一个完美的递归解决方案： 当我构建一个递归解决方案时，我不会太多思考。我只是试图理解更小的子问题。 选项1: 我添加当前索引中的值，并转到索引+2 选项2: 我不添加当前索引中的值，并从索引+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并输入了我的解决方案，但似乎无法得到递归树以及它在哪里失败了。 请问有人能够给我一个正确的记忆化实现，同时保持整体结构不变吗？换句话说，我不想改变递归函数的定义。

- ababuji

Answer 1

你的记忆化方法不起作用，因为当你到达某个索引 i 时，如果你已经计算出 i 的一些结果，你的算法无法考虑到可能有一个更优的结果可通过抢劫数组左侧更优秀的房屋集来获得。

解决这个问题的方法是避免将运行的值（你抢了多少钱）从父节点向子节点传递。思路是在没有任何祖先节点的输入的情况下计算子问题的结果，然后在回溯调用堆栈时从较小的结果构建较大的解决方案。

索引 i 的记忆化将会起作用，因为给定的索引 i 将始终具有一组唯一的子问题，其解决方案不会受到数组左侧祖先选择的损坏。这保留了DP所必需的最优子结构。

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

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

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

if __name__ == "__main__":
    print(maximize_robberies([1, 2, 1, 1], {}))

- ggorlen

---

谢谢ggorlen，我得选择Michael的答案，因为他没有改变整体结构。感谢你所提供的解释。 - ababuji

很遗憾，没有足够的方式来表达感谢之情。 :) - ababuji

Answer 2

helper可以使用不同的value参数来调用相同的index。因此，必须删除（从存储的max_dict中减去）value。一种方法是在返回之前添加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的回答，他给出了更详细的解释。

- Michael Butscher

Answer 3

我使用以下方法解决了这个动态规划问题。并且它在O(n)时间内发生。请尝试。

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def rob(self, nums):
            n = len(nums)
            if n==0:
                return 0;
            if n == 1:
                return nums[0]
            s = [0]*(n+1)
            s[1] = nums[0]
            s[2] = nums[1]

            for i in range(3,n+1):
                s[i] = (max(s[i-2],s[i-3]) + nums[i-1])
            return max(s[n],s[n-1])


    money = [2, 1, 1, 2]
    sol = Solution()
    print(sol.rob(money))

- Shagun Pruthi

---

谢谢！但我早就得到了这个答案。 - ababuji