# Python Straight Forward Solution

• 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 []``````

• 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]``````

• @sha256pki
Very clear 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:]``````

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

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