迷宫中的小偷[关闭]

Question

我有一个练习的问题：

我们有一个能量为k的小偷和一个迷宫（n×m）给出的数值矩阵作为自然数。所以小偷从左上角开始向下走。他的目标显然是尽可能地用他的能量偷走。对于每一步，他都使用1个单位的能量。

他可以通过两种方式行动：

1. 他可以向前迈出一步
2. 他可以跳到下一行的第一列

（所以他从左边偷走每一行'。）

当他耗尽精力时，他会离开迷宫（我认为他可以跳出迷宫，而不是终点线）。

例如，我理解迷宫中的鼠标（鼠标吃尽可能多的奶酪），但我不知道如何在这里包括能量。

如何为这个问题编写递归方程？

是否有DP解决方案（即使用矩阵操作）？

Answer 1

以下递归函数将输出最大可能战利品的元组以及在行列元组列表中实现它的路径：

def steal(maze, energy, row=0, column=0):
    if energy <= 0 or row >= len(maze) or column >= len(maze[row]):
        return 0, []
    loot, path = max(
        steal(maze, energy - 1, row, column + 1),
        steal(maze, energy - 1, row + 1, 0)
    )
    return maze[row][column] + loot, [(row, column)] + path

例如：

m = [
    [2, 8, 3],
    [6, 5, 1],
    [9, 4, 7]
]
print(steal(m, 5))

将输出：

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

Answer 2

这个问题在某些方面类似于背包问题。你可以用dp或递归来解决它。看看this链接，它会让你更好地理解这个问题。你的问题有点不同但逻辑是一样的。