Python Straight Forward Solution


  • 2

    I used DP. dp[i] represent the best path found to get to the place indexed i + 1 and dp[i][0] is the cost of the path.
    dp[0] is initialized as [A[0], 1] and the others are initialized as [infinity].

    def cheapestJump(self, A, B):
            if not A or A[0] == -1: return []
            dp = [[float('inf')] for _ in A]
            dp[0] = [A[0], 1]
            for j in range(1, len(A)):
                if A[j] == -1: continue
                dp[j] = min([dp[i][0] + A[j]] + dp[i][1:] + [j + 1] for i in range(max(0, j - B), j))
            return dp[-1][1:] if dp[-1][0] < float('inf') else []

  • 2
    S

    Similar to what I did, except yours is more concise

    class Solution(object):
        def cheapestJump(self, A, B):
            """
            :type A: List[int]
            :type B: int
            :rtype: List[int]
            """
            n = len(A)
            dp =   [ float('inf')] * n
            path = [[]] * n
            dp[0]   = 0    # dp[i]   = cost it takes to jump at i
            path[0] = [1]  # path[i] = path to i from first place
            for i in range(1, n):
                if A[i] == -1:
                    continue
                for j in range(max(0,i-B), i):
                    if dp[i] > (A[i] + dp[j]):
                        path[i] = path[j] + [i+1] # [i+1] because indexing starts at 1
                        dp[i]   = A[i] + dp[j]
                    elif dp[i] == (A[i] + dp[j]):    # if path costs are same 
                        if path[i] > path[j] + [i+1]: # then chose lexicographically smaller path
                            path[i] = path[j] + [i+1]
                        
            return path[n-1]

  • 0

    @sha256pki
    Very clear solution.


  • 0
    J

    @lee215 said in Python Straight Forward Solution:

    Same idea,but a top-bottom recursive solution:)

        memo={len(A)-1:[A[-1],len(A)]}
        def dp(i):
            if i not in memo:
                memo[i]=[float('inf')]
                for j in xrange(1,B+1):
                    if i+j<len(A) and A[i+j]!=-1:
                        memo[i]=min([A[i]+dp(i+j)[0]]+[i+1]+dp(i+j)[1:],memo[i])
            return memo[i]
        return dp(0)[1:]

  • 0
    L

    @sha256pki
    You only need to compare path[i]>path[j] in your elif


Log in to reply
 

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