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):
            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.