Need Help Writing Recursive function that find cheapest route through a list of numbers

Question

So I've been working on this homework problem for a few hours, I'll do my best to explain it.

I need to write a program in python that takes a list and starts you at the first item in the list, you can either move forward one space or jump over an item and land on the other side of it, each item you land on costs the number on that location. The goal is to get to the end as cheaply as possible.

I wrote this function,

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

but it can't see past the next two positions, so it might make mistakes. A good example is this list [0,1,2,1000,0] my program outputs 3 because it picks 1 over 2, then 2 over a 1000, then 0. This adds up to 3, but the fastest way is jump to 2, then to 0.

In the homework it says it might take a long time to run long lists, I'm guessing they want me to try every possible combination of jumps and pick the cheapest one but I don't see how to do that with using recursion.

EDIT: So this is the improvement I made based off of the comments, It works with all the examples my prof. gave me except for one, this is the list it doesn't return what he said it should. [0, 98, 7, 44, 25, 3, 5, 85, 46, 4] He says it should return 87, but my adjusted program returns 124. Here's the new code:

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

The following should work:

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

Example:

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

This can be actually considered a dynamic programming algorithm. If c(i) denotes the best cost for the subproblem that uses the first i entries then:

c(1) = cost of first element

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

For i > 2 either the best cost is either the best solution reaching the i - 1th element and then including the ith element or the best solution reaching the i - 2th element and then jumping to the ith element. So

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

The above relation explains the short loop in the code, where a, b are the currently last two best costs.

A recursive version would be like this:

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

This recursive program performs an operation to the previous 2 values of the function, in a similar way as the naive recursive function of fibonnaci. It's easy to claim that the above version needs also exponential time. To avoid it, we should use memoization, which means to cache the results of the intermediate recursive calls:

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]