Minimum time to cross all checkpoints

The idea is to use a recursive approach to find the minimum time to reach Ninjaland. The recursive idea is very clear that for any checkpoint at any of the two lanes, there are only two choices, either continue moving along the same lane or switch between the two lanes. Using this idea we can calculate the minimum travel time recursively.

We will define a function GET_MIN_TIME(i,j) to find the minimum time it takes to reach Checkpoint i at Lane-j. After defining the function, we can call it to find the Minimum Time it takes to reach Checkpoint ‘N’, at Lane-0 and Lane-1. Our final answer will be the Minimum among the two values.

Working of the Recursive function: 

1. If i is equal to 1, then we will return TIME[0][j]. This will serve as the base case for our recursive function. Note that for Checkpoint-1 there is only 1 choice.
2. If j is equal to 0, then we will return the minimum value among GET_MIN_TIME(i-1,0) + Time[i-1][0] and GET_MIN_TIME(i-1,1) + CHECKPOINTS[i-2][1]. As we can see that to reach Checkpoint ‘i’ at Lane-0 there are only two choices, either come to Checkpoint i-1 at Lane-0, and move along the same lane, come to Checkpoint i-1 at Lane-1, and switch lanes. So, we are comparing the two results and taking the minimum value among them.
3. Otherwise,  we will return the minimum value among GET_MIN_TIME(i-1,1)+Time[i-1][1] and GET_MIN_TIME(i-1,0)+CHECKPOINTS[i-2][0]. As we can see that to reach Checkpoint ‘i’ at Lane-1 there are only two choices, either come to Checkpoint ‘i-1’ at Lane-1, and move along the same lane, come to Checkpoint ‘i-1’ at Lane-0, and switch lanes. So, we are comparing the two results and taking the minimum value among them.

In the previous approach, the function 'GET_MIN_TIME'(i,j) is recursively being calculated several times for some fixed values of i and j. So, here we can use the technique of 'memoization to optimize the working of the previous approach. We will create a 2D Matrix to store all the previously computed values, so that no value is being calculated multiple times. We will make a 2D array 'MEMO' having N+1 rows and 2 columns with all values initialized as -1, 'MEMO'[i][j] will denote the minimum time to reach the Checkpoint i at Lane-j. Note that the working here is the same as the previous approach, just that we will modify the recursive function, so that it does not calculate the same answer twice. 

Working of the Recursive function: 

1. If 'MEMO'[i][j] is not equal to -1, then we will return 'MEMO'[i][j] as we have already computed its value, and we need not to compute it again.
2. If i is equal to 1, then we will set 'MEMO'[i][j] as TIME[0][j] and return 'MEMO'[i][j]. This will serve as the base case for our recursive function. Note that for Checkpoint-1 there is only 1 choice.
3. If j is equal to 0, then we will set 'MEMO'[i][j] as the minimum value among 'GET_MIN_TIME'(i-1,0) + Time[i-1][0] and 'GET_MIN_TIME'(i-1,1) + CHECKPOINTS[i-2][1], and return 'MEMO'[i][j].
4. Otherwise,  we will we will set 'MEMO'[i][j] as the minimum value among 'GET_MIN_TIME'(i-1,1) + Time[i-1][1] and 'GET_MIN_TIME'(i-1,0) + CHECKPOINTS[i-2][0], and return 'MEMO'[i][j].

In the first approach, the function 'GET_MIN_TIME' recursively calculates the time it takes to cross all the checkpoints  which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use Dynamic Programming to overcome the overlapping subproblems. So we will convert the 'GET_MIN_FUNCTION' to a 2-D array having N and 2 columns to store the DP states. Let 'GET_MIN_TIME[i][j]’ denotes the minimum Time to reach Checkpoint ‘i + 1’ at Lane ‘j’.

The recursive relation to find out 'GET_MIN_TIME[i][j]’ can be written as : 

1. 'GET_MIN_TIME[i][0]’ = min('GET_MIN_TIME[i-1][0]’ + TIME[i][0] , 'GET_MIN_TIME[i-1][1]’ + ‘CHECKPOINTS[i-1][1]’ 
2. 'GET_MIN_TIME[i][1]’ = min('GET_MIN_TIME'[i-1][1] +TIME[i][1] , 'GET_MIN_TIME'[i-1][0] + CHECKPOINTS[i-1][0]

Taking the base case as 'GET_MIN_TIME[0][0]’ = ‘TIME[0][0]’ and 'GET_MIN_TIME[0][1]’ = ‘TIME[0][1]’. 

If we observe carefully, we are finding the value of 'GET_MIN_TIME[i][j]’ in the same manner we were finding values using the function 'GET_MIN_TIME(i,j)’. The major difference is that we have stored all our previously computed values to save redundancy. 

This approach works fine but we are using an extra 2-D array, we can also optimize that if we observe that to compute the i'th row we only need the values of (i-1)'th row. So, there is no need to store all the previous values. We can just store the previous row values for our calculations and update them as we move ahead.

Steps:

1. Let 'PREV' be an array of size 2 to store the minimum time to reach the last visited checkpoints.
2. Initialize 'PREV'[0] to TIME[0][0], and 'PREV'[1] to TIME[0][1] as the base case.
3. Iterate from ‘i’ = 1 to ‘N’ - 1
   • Make a new array ‘CURR’ to store the minimum time to reach the checkpoints currently under consideration.
   • Set CURR[0] to the minimum value among 'PREV'[0]+TIME[i][0] and 'PREV'[1] + CHECKPOINTS[i-1][1].
   • Similarly, set CURR[1] to the minimum value among 'PREV'[1]+TIME[i][1] and 'PREV'[0] + CHECKPOINTS[i-1][0].
   • Set 'PREV'[0] as CURR[0] and set 'PREV'[1] as CURR[1], as these values will be used for computation of minimum time for the next checkpoint.
4. Return the minimum value among 'PREV'[0] and 'PREV'[1] as the final answer.