Python with functools.lru_cache


  • 0

    My best(i) returns the cost of the best path starting at position i as well as the path.

    from functools import lru_cache
    
    class Solution:
        def cheapestJump(self, A, B):
            @lru_cache(None)
            def best(i):
                if A[i-1] == -1:
                    return math.inf, []
                if i == len(A):
                    return A[i-1], [i]
                cost, path = min(map(best, range(i+1, min(i+B, len(A))+1)))
                return A[i-1] + cost, ([i] + path) * (cost != math.inf)
            return best(1)[1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.