改装房屋强盗

Question

我一直在对入室盗窃问题进行轻微修改。

我能够生成递归关系并对其进行编程以找到最大总数。

def mod_robber(arr):
  arr[1] = max(arr[0], arr[1])
  for i in range(2, len(arr)):
    arr[i] = max(arr[i]+arr[i-2], arr[i-1])
  return arr[-1]

不过，我想找哪所要抢的房子。例如;如果我给它数组 [1, 2, 3, 1] 它适当地 returns 4，但我希望它 return [1, 3].

这是一种自下而上的方法，我用最新的最大值填充列表的每个索引，然后 return 最后一个元素。所以，在这个例子中； [1, 2, 3, 1] 在运行循环之后变为 [1, 2, 4, 4]，其中 4 是我们的最大值。

我暗暗怀疑我应该反向遍历修改后的列表 [1, 2, 4, 4]，然后从最大值中减去。但我想不出一种在所有情况下都能正常工作的方法。

我也找到了thispost，问了一个类似的问题。但是给出的答案都计算了最大总和，而不是 return 适当的索引。

非常感谢您的集体智慧。

Answer 1

您可以创建一个用贡献索引扩展的列表。所以一开始，每个值的贡献索引只有一个：它自己的索引。对于示例输入，我们将从以下内容开始：

[(1, (0,)), (2, (1,)), (3, (2,)), (1, (3,))]

然后就是将两个条目正确相加的问题了：

def mod_robber(arr):
    arr = [(val, (i,)) for i, val in enumerate(arr)]
    arr[1] = max(arr[0], arr[1])
    for i in range(2, len(arr)):
        arr[i] = max((arr[i-2][0] + arr[i][0], arr[i-2][1] + (i,)), arr[i-1]) 
    return arr[-1]

您的示例的输出是：

(4, (0, 2))

...表示最大值为4，贡献索引为0和2（从零开始的索引号）。

改装房屋强盗

Modified House Robber

python

algorithm

list

dynamic