Paths requiring minimum number of jumps to reach end of array | Java Program to implement the above approach ; Pair Class instance ; Stores the current index ; Stores the path travelled so far ; Stores the minimum jumps required to reach the last index from current index ; Constructor ; Minimum jumps required to reach end of the array ; Stores the maximum number of steps that can be taken from the current index ; Checking if index stays within bounds ; Stores the minimum number of jumps required to jump from ( i + j ) - th index ; Function to find all possible paths to reach end of array requiring minimum number of steps ; Storing the neighbours of current index element ; Function to find the minimum steps and corresponding paths to reach end of an array ; Stores the minimum jumps from each position to last position ; Driver Code
import java . util . * ; class GFG { public static class Pair { int idx ; String psf ; int jmps ; Pair ( int idx , String psf , int jmps ) { this . idx = idx ; this . psf = psf ; this . jmps = jmps ; } } public static int [ ] minJumps ( int [ ] arr ) { int dp [ ] = new int [ arr . length ] ; Arrays . fill ( dp , Integer . MAX_VALUE ) ; int n = dp . length ; dp [ n - 1 ] = 0 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int steps = arr [ i ] ; int min = Integer . MAX_VALUE ; for ( int j = 1 ; j <= steps && i + j < n ; j ++ ) { if ( dp [ i + j ] != Integer . MAX_VALUE && dp [ i + j ] < min ) { min = dp [ i + j ] ; } } if ( min != Integer . MAX_VALUE ) dp [ i ] = min + 1 ; } return dp ; } public static void possiblePath ( int [ ] arr , int [ ] dp ) { Queue < Pair > queue = new LinkedList < > ( ) ; queue . add ( new Pair ( 0 , " " + 0 , dp [ 0 ] ) ) ; while ( queue . size ( ) > 0 ) { Pair tmp = queue . remove ( ) ; if ( tmp . jmps == 0 ) { System . out . println ( tmp . psf ) ; continue ; } for ( int step = 1 ; step <= arr [ tmp . idx ] ; step ++ ) { if ( tmp . idx + step < arr . length && tmp . jmps - 1 == dp [ tmp . idx + step ] ) { queue . add ( new Pair ( tmp . idx + step , tmp . psf + " ▁ - > ▁ " + ( tmp . idx + step ) , tmp . jmps - 1 ) ) ; } } } } public static void Solution ( int arr [ ] ) { int dp [ ] = minJumps ( arr ) ; possiblePath ( arr , dp ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 3 , 3 , 0 , 2 , 1 , 2 , 4 , 2 , 0 , 0 } ; int size = arr . length ; Solution ( arr ) ; } }