Python O(nB)


  • 0
    X
    class Solution(object):
        def cheapestJump(self, A, B):
            """
            :type A: List[int]
            :type B: int
            :rtype: List[int]
            """
            asz = len(A)
            bt = [-1] * asz  # backtrack
            cost = [float('inf')] * asz
            cost[-1] = A[-1]
            for hi in reversed(range(asz)):
                if A[hi] == -1 or cost[hi] == float('inf'):
                    continue
                for lo in range(max(0, hi-B), hi):
                    if A[lo] == -1:
                        continue
                    c = cost[hi] + A[lo]
                    if c <= cost[lo]:
                        cost[lo] = c
                        bt[lo] = hi
            
            if cost[0] == float('inf'):
                return []
            
            p = [0]
            while bt[p[-1]] > 0:
                p.append( bt[p[-1]] )
            return [i+1 for i in p]          
    

Log in to reply
 

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