Python solution with heapq


  • 0
    Z
    class Solution(object):
        def cheapestJump(self, A, B):
            """
            :type A: List[int]
            :type B: int
            :rtype: List[int]
            """
            #
            # some trick part
            #
            dp = collections.defaultdict(list)
            heapq.heappush(dp[0],(A[0],[1]))
            for i in range(1,len(A)):
                if A[i]==-1:
                    continue
                j = i-1
                while j>=0 and i-j<=B:
                    if A[j]==-1 or len(dp[j])==0:
                        j-=1
                        continue
                    #for elem in dp[i]:
                    #print(i,j)
                    #print(dp)
                    heapq.heappush(dp[i],(dp[j][0][0]+A[i],dp[j][0][1]+[i+1]))
                    j-=1
            
            if len(dp[len(A)-1])==0:
                return []
            else:
                return dp[len(A)-1][0][1]

Log in to reply
 

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