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

Question

所以我一直在做这个家庭作业问题几个小时,我会尽力解释它.

我需要在python中编写一个程序来获取列表并在列表中的第一个项目处启动,您可以向前移动一个空格或跳过一个项目并在其另一侧着陆,每个项目都会降低成本该位置的号码.目标是尽可能便宜地达到目的.

我写了这个函数,

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因为它选择1超过2,然后超过1000,然后是0.这加起来为3,但最快的方法是跳转到2,然后到0.

在家庭作业中它表示可能需要很长时间来运行长列表,我猜他们希望我尝试每种可能的跳转组合并选择最便宜的组合,但我不知道如何使用递归.

编辑: 所以这是我根据评论做出的改进,它适用于我教授的所有例子.给了我除了一个,这是它没有返回他说的应该的列表.[0,98,7,44,25,3,5,55,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

这实际上可以被认为是动态编程算法.如果c(i)表示使用第一个i条目的子问题的最佳成本,则:

c(1)=第一元素的成本

c(2)=前两个要素的成本之和

对于i > 2任一最佳的成本要么是最好的解决方案在到达i - 1第i个元素,然后包括ith元素或最佳的解决方案在到达i - 2第i个元素,然后跳到i个元素.所以

c(i)= min(c(i-1),c(i-2))+ i元素的成本

上面的关系解释了代码中的短循环,其中a,b是目前最后两个最佳成本.

递归版本是这样的:

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

该递归程序以与fibonnaci的朴素递归函数类似的方式对函数的前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]