## Problem Statement

Here we have a problem statement, Paths requiring a minimum number of jumps to reach the end of the array.

Here we have the problem of finding all the possible paths, requiring minimum jumps to reach the end of the array. For better understanding, letâ€™s discuss the problem with the help of an example.

Input Array: arr[]= { 3 , 3 , 0 , 2 , 1 , 0 }

Output : 0-> 3->5

Here above is the path we follow for 0-based indexing for the input array. The minimum value for the jump is 3, and there is only one path possible for the minimum jump to reach the end of the array.

Now understand it more descriptively:

- Here in the Input Array, we have given how to extend the index we may jump from the present index. I.e. for 0 indexes, we have a choice up to 0+3 =3 index value we go either 1, 2, or 3. In the similar way we have for the index 1, with value 1+3=4 index we either go to 2, 3 or 4, similar for the 2 indexes with 0 value we reside 2+0=2 index itself its a blockage, similar for 3 indexes with the value of jump 2, we go up to 3+2=5 index we have a choice for 4 or 5. For index value 4 with the value of jump 1, we have 4+1=5 index, similar to the last reaching index value 5 here we have 0 as always as we have reached the destination or end of the array.
- Here in the Dp-Array, we are storing the minimum jumps we require to reach the destination of the array. That is the meaning of the Dp-Array, now. We go with the smaller problem to store the value, so we start filling the DP array in the backward direction.
- For the storage in the backward direction, for index=5, as its last, we have itself at the last index, so in dp array which has information for minimum jumps to reach the destination index or end of array from their index, now for index=4, we have arr[4] =1, so we have max extent for the jump is 1, so in dp[4]=1.
- Now for the index =3, we have arr[3]=2 we have extended up to 2 indexes, i.e. 4 or 5, if we have chosen 4 then we have to go 5 again, which require 2, as we choose 5 then it 1, so for that, we considered for the minimum part, so we choose 5 and dp[3]=1.
- Now for the index =2, we have arr[2]=0, as we have an extent of jump value is 0, so we have a blockage, so dp[2]=null.
- Now for the index=1, we have arr[1]=3, we have chosen for 2, 3 or 4 indexes as jump up to 3 indexes, so for we choose the minimum value plus additional itself own, now arr[2]=null, arr[3]=1 and arr[4]=1, as we have minimum 1 value we have a choice for both, we take any of the paths either by 3 or 4 value, so dp[1]=2.
- Now for the index=0, we have the arr[0]=3 so we have 1, 2, or 3 choices, as seeing arr[1]=2, arr[2]=null, and arr[3]= 1, as seeing the value of all the three index value of array, we have a minimum at 3, i.e. 1 for reaching destination point with a minimum jump. So we choose the value 1, so dp[0]=2.

The above illustration shows the filling meaning for the Dp-Array, properly, if we iterate the same in the way, for minimum jump, we find that we have an answer column, with 0 -> 3 -> 5, we require a minimum 3 jumps to reach the end of the array.

Also Read About, __Byte Array to String__

## Approach for Solution

Now letâ€™s think about solving the problem in a better way; as we have to find the minimum jumps, path possible to reach the end of the array, we are getting the Dynamic Programming Approach for the minimal value of the jump to reach the end of the array.

Now understand the way of steps manner to solve the problem are as follow:-

- Firstly we understand the meaning of the given input array, which shows the maximum number of jumps or steps we take forward from that element at every index.
- Then it just became the problem of finding the minimum number of jumps to reach the end of the array, i.e. Jump Game II but here, we have to also trace the path for that finding.
- For that, we declare a dp array for finding the minimum number of jumps to reach the destination of the array at every index; how many jumps are required? We have to calculate it. This can be done by the concept of dynamic programming for solving the small problem first. For the bigger problem, we have started filling the DP-array from the backward direction, which implementation is explained above in the Explanation of the problem statement.
- Now, after creating the Dp- Array, we have the process of reverse engineering sort of thing, as we fill Dp- Array in backward then start traversing the Dp-Array in forwarding direction.
- To do reverse engineering, we are required to store some Information, to aim our answer to print the possible path for minimum jump, so we declare another class for which it has the information of index we are working, allowed_jump at particular index from the input array, minimum_jum_calculated for each index in Dp-Array to reach the end of the array and path_calculated_soFar for the possible pathfinding for the minimum jump.
- In this way, we followed the steps and did our task.