Problem statement

https://leetcode.com/problems/coin-path/

Solution 1

One of the ways to solve this problem is to use dp. Let dp[i] be pair: price we need to pay to go from position i to the end and next position we need to go from place i. Note, that if we want to have lexicographically minimum solution, we need to start from the end. How we can update dp[i]: we look all B places which can be reached from this place: all of them already calculated and choose the best one.

Complexity

Time complexity is O(Bn), space complexity is O(n)

Code

class Solution:
    def cheapestJump(self, A, B):
        result, n, k = [], len(A), 0
        dp = [[float("inf"), -1] for _ in range(n)] 
        dp[-1] = [A[n-1], -1]
        
        for i in range(n-1, -1, -1):
            if A[i] == -1: continue
            for j in range(i+1, min(i+B+1, n)):
                dp[i] = min(dp[i], [A[i] + dp[j][0], j])
                
        if dp[0][0] == float("inf") or A[-1] == -1: return result
        
        while k != -1:
            result.append(k+1)
            k = dp[k][1]
        return result

Solution 2

Note, that there is also O(n) time complexity solution, which use the idea of problem 0239 Sliding Window Maximum. Actually this problem is almost identical to 1696. Jump Game VI (and almost as 1425 Constrained Subsequence Sum) with only difference here that we need to reconstruct answer. Another difficulty is that we need to get answer with the smallest lexicographical order and if we do it for nums, the answer will be the largetst, not smallest. We can reverse nums and start to construct answer from the end.

Complexity

It is O(n) for time and space

Code

class Solution:
    def cheapestJump(self, nums, k):
        nums = [i if i != -1 else float("inf") for i in nums][::-1]
        deq, back, n = deque([0]), {}, len(nums)

        for i in range(1, n):
            while deq and deq[0] < i - k: deq.popleft()
            back[i] = deq[0]
            nums[i] += nums[deq[0]]   
            while deq and nums[i] <= nums[deq[-1]]: deq.pop()
            deq.append(i)

        if nums[-1] == float("inf"): return []
        
        end, ans = n - 1, [1]

        while end:
            end = back[end]
            ans.append(n - end)
        
        return ans