记忆化问题 - 房屋强盗问题

Question

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

所以这是问题陈述：

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

示例：

Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

另一个：

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

还有一个

Input: [2, 1, 1, 2] Output: 4 Explanation: Rob house 1 (money = 2) and then rob house 4 (money = 2). Total amount you can rob = 2 + 2 = 4.

现在就像我说的，我有一个完美的递归解决方案：当我构建一个递归解决方案时。我不想太多。我只是想了解更小的子问题是什么。

option_1：我在当前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

这非常有效.. returns 正确的值 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

对于相同的 index，可以使用不同的 value 参数调用 helper。因此必须删除 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 的回答给出了更详细的解释

Answer 2

您的记忆方法将不起作用，因为当您达到某个索引 i 时，如果您已经为 i 计算了一些结果，您的算法将无法考虑可能存在的事实更好的结果可以通过在数组的左侧部分抢劫一组更优化的房屋来获得。

这个困境的解决方案是避免通过从parents到children的递归调用向下传递运行value（你抢的钱）。这个想法是在没有来自祖先节点的 任何输入 的情况下计算 sub-problem 结果，然后在返回调用堆栈的路上从较小的解决方案构建较大的解决方案。

索引 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], {}))

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))

记忆化问题 - 房屋强盗问题

Issue with memoization - House Robber problem

python

recursion

memoization

dynamic-programming

python-3.x