python - 需要帮助编写通过数字列表找到最便宜路线的递归函数

Question

所以我已经在这个家庭作业问题上工作了几个小时，我会尽力解释它。

我需要用 python 编写一个程序，它接受一个列表并从列表中的第一项开始，你可以向前移动一个空格或跳过一个项目并落在它的另一边，每个项目你land on 花费那个位置的数字。目标是以尽可能低的成本到达终点。

我写了这个函数，

def player(cost, board, player_pos):
    if player_pos == (len(board)) - 1:    
        return cost
    if player_pos < (len(board)) - 2:     
        if board[player_pos + 1] > board[player_pos + 2]:
            return player(cost + board[player_pos + 2], board, player_pos + 2)
        else:
            return player(cost + board[player_pos + 1], board, player_pos + 1)
    elif player_pos == (len(board)) - 2:
        return (cost + board[player_pos] + board[player_pos + 1])

但它无法看到接下来的两个位置，所以它可能会出错。一个很好的例子是这个列表 [0,1,2,1000,0] 我的程序输出 3，因为它从 2 中选择 1，然后从 1000 中选择 2，然后是 0。这加起来是 3，但最快的方法是跳转到2，然后到0。

在家庭作业中它说运行长列表可能需要很长时间，我猜他们希望我尝试所有可能的跳跃组合并选择最便宜的，但我不知道如何使用递归。

编辑: 所以这是我根据评论所做的改进，它适用于我教授的所有示例。给了我一个，这是一个列表，它没有返回他所说的应该返回的内容。 [0, 98, 7, 44, 25, 3, 5, 85, 46, 4] 他说它应该返回 87，但我调整后的程序返回 124。这是新代码:

def player(cost, board, player_pos):
    if player_pos == (len(board)) - 1:    
        return cost
    if player_pos < (len(board)) - 2:     
        if (player(cost + board[player_pos + 2], board, player_pos + 2)) < (player(cost + board[player_pos + 1], board, player_pos + 1)):
            return player(cost + board[player_pos + 2], board, player_pos + 2)
        else: return player(cost + board[player_pos + 1], board, player_pos + 1)
    elif player_pos == (len(board)) - 2:
        return (cost + board[player_pos] + board[player_pos + 1])

Answer 1

以下应该有效:

def player(l):
    a = b = l[0]
    for v in l[1:]:
        a, b = b, min(a, b) + v
    return b

例子:

>>> player([0, 98, 7, 44, 25, 3, 5, 85, 46, 4])
87

这实际上可以认为是一个dynamic programming算法。如果 c(i) 表示使用第一个 i 条目的子问题的最佳成本，则:

c(1) = cost of first element

c(2) = sum of costs of first two elements

对于 i > 2 要么最佳成本要么是达到第 i - 1 个元素然后包括第 i 个的最佳解决方案元素或到达第 i - 2 元素然后跳转到第 i 元素的最佳解决方案。所以

c(i) = min(c(i - 1), c(i - 2)) + cost of ith element

上面的关系解释了代码中的短循环，其中a，b是当前最后两个最好的代价。

递归版本是这样的:

def player(l):
    return min(player(l[:-1]), player(l[:-2])) + l[-1] if l else 0

此递归程序对函数的前 2 个值执行操作，其方式与斐波那契的朴素递归函数类似。很容易声称上述版本也需要指数时间。为了避免它，我们应该使用 memoization ，这意味着缓存中间递归调用的结果:

def player(l, cache=None):
    n = len(l)
    if cache is None:
        cache = [-1] * (n + 1)
    if cache[n] < 0:
        cache[n] = min(player(l[:-1], cache), player(l[:-2], cache)) + l[-1] if l else 0
    return cache[n]