Coin Path - Leetcode Solution

Coin Path problem on leetcode can be solved using dynamic programming. The problem statement is as follows:

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 within the array boundary.

Now, the main objective of the problem is to find a minimum cost path to reach the last index of the array A (index N) from the first index of the array A (index 1), such that the path consists of a sequence of indices (i1, i2, ..., im) satisfying the following conditions:

1. (i1, i2, ..., im) is a valid sequence of indices. That means: 1 ≤ i1 < i2 < ... < im ≤ N.
2. For all 1 ≤ j < m, we have either ij+1 = ij + 1 or ij+1 - ij ≤ B.
3. The cost of the path is the sum of the absolute differences of consecutive pairs of integers in the path. That is, the cost is ∑_{j=1}^{m-1} |Aj - Aj+1|.

For example, consider the following input:

A = [1,2,4,-1,2], B = 2

The minimum cost path that satisfies the conditions mentioned above is [1,3,5]. The cost of this path is |1-4| + |4-2| = 5.

The solution of the problem can be obtained in the following way:

1. Firstly, we will create a 1D array dp of size N+1 where dp[0] = 0 and dp[1] = |A1|.

2. We will then iterate through the array A from indices i=2 to i=N and compute the optimal solution for each index. The optimal solution for index i will be the minimum cost path that reaches index i from any of the preceding indices.

3. For each index i, we will loop through all the preceding indices j (where j ≤ i-B and j > 0). For each preceding index j, we will compute the cost of the path from index j to index i and add it to the dp[j] value. If this cost is less than the current dp[i] value, then we will update the dp[i] value.

4. Finally, the minimum cost path to reach index N will be stored in dp[N].

5. A path that satisfies the conditions mentioned above can be generated by iteratively moving through the indices of A from N to 1 and selecting the index that leads to the minimum dp value.

The time complexity of the above algorithm is O(NB), and the space complexity is O(N).

The following is the Python implementation of the above algorithm:

def coinPath(A, B):

N = len(A)
dp = [0]*(N+1)
idx = [-1]*N

dp[0] = 0
dp[1] = abs(A[0])

for i in range(2,N+1):
    for j in range(max(1,i-B),i):
        cost = dp[j] + abs(A[i-1]-A[j-1])
        if dp[i]==0 or cost<dp[i]:
            dp[i] = cost
            idx[i-1] = j-1
            
path = []
i = N-1
while i>=0:
    path.append(i+1)
    i = idx[i]

path.reverse()
return path

1