LC 656. Coin Path 【lock, Hard】

Given an array A (index starts at 1) consisting of N integers: A1, A2, ..., AN and an integer B. The integer B denotes that from any place (suppose the index is i) in the array A, you can jump to any one of the place in the array A indexed i+1, i+2, …, i+B if this place can be jumped to. Also, if you step on the index i, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexed i in the array.

Now, you start from the place indexed 1 in the array A, and your aim is to reach the place indexed Nusing the minimum coins. You need to return the path of indexes (starting from 1 to N) in the array you should take to get to the place indexed N using minimum coins.

If there are multiple paths with the same cost, return the lexicographically smallest such path.

If it's not possible to reach the place indexed N then you need to return an empty array.

Example 1:

Input: [1,2,4,-1,2], 2
Output: [1,3,5]

Example 2:

Input: [1,2,4,-1,2], 1
Output: []

Note:

Path Pa1, Pa2, ..., Pan is lexicographically smaller than Pb1, Pb2, ..., Pbm, if and only if at the first iwhere Pai and Pbi differ, Pai < Pbi; when no such i exists, then n < m.
A1 >= 0. A2, ..., AN (if exist) will in the range of [-1, 100].
Length of A is in the range of [1, 1000].
B is in the range of [1, 100].

参考了lee215的解答：

设dp数组中dp[i]为到第i个位置最小花费，那么dp数组就可以求出来。递推公式为

for i in 1 : len:

dp[i] = min(dp[j] + A[i-1]) for j in range(max(0,j-B),j)

大意就是从当前位置往回找B个位置，并把之前的花费和当前的A相加，求最小值。

而又要返回字典序的最小index。在python中可以用min求数组的最小，就是字典序。

Runtime: 236ms, beats 24.14% 时间复杂度（N*B*N），最后一个N是因为比较数组的时候，数组长度是N，空间复杂度（N*N）

class Solution:
    def cheapestJump(self, A, B):
        """
        :type A: List[int]
        :type B: int
        :rtype: List[int]
        """
        if not A or A[0] == -1: return 0
        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 []

看来还能再优化，

这是另一种解法，利用堆的性质，同样把花费和路径都放进堆中，每次取最小的一个花费，加上当前的花费再推进堆中。时间复杂度（N*log(B)*N）,优化了选取的步骤，但堆中元素每一次比较花费的时间还是O（N）的。

Runtime：68ms beats: 100%

def cheapestJump(self, A, B):
        
        N = len(A)
        A = ['dummy'] + A
        if A[N] == -1: return []
        heap = [(A[N], [N])]
        new_path = [N]
        for i in range(N-1, 0, -1): # From N-1 sweeping to 1
            if A[i] == -1: continue
            
            while heap:
                cost, path = heapq.heappop(heap)
                if path[0] <= i + B: break #当前的index加上B后应该大于之前保存的路径的第一个，这样才能连的上。

            else: # exhausted heap without finding the previous path
                return []
            
            new_cost = cost + A[i]
            new_path = [i] + path
            
            heapq.heappush(heap, (new_cost, new_path))
            heapq.heappush(heap, (cost, path))
        return new_path

这题如果用C++,JAVA来做，没有python的min能比较数组或者tuple的性质就麻烦一点。