Minimum number of jumps to reach end | Returns Minimum number of jumps to reach end ; jumps [ 0 ] will hold the result ; Minimum number of jumps needed to reach last element from last elements itself is always 0 ; Start from the second element , move from right to left and construct the jumps [ ] array where jumps [ i ] represents minimum number of jumps needed to reach arr [ m - 1 ] from arr [ i ] ; If arr [ i ] is 0 then arr [ n - 1 ] can 't be reached from here ; If we can direcly reach to the end point from here then jumps [ i ] is 1 ; Otherwise , to find out the minimum number of jumps needed to reach arr [ n - 1 ] , check all the points reachable from here and jumps [ ] value for those points ; initialize min value ; following loop checks with all reachable points and takes the minimum ; Handle overflow ; or INT_MAX ; Driver Code
< ? php function minJumps ( $ arr , $ n ) { $ jumps [ $ n ] = array ( ) ; $ min ; $ jumps [ $ n - 1 ] = array ( 0 ) ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { if ( $ arr [ $ i ] == 0 ) $ jumps [ $ i ] = PHP_INT_MAX ; else if ( $ arr [ $ i ] >= ( $ n - $ i ) - 1 ) $ jumps [ $ i ] = 1 ; else { $ min = PHP_INT_MAX ; for ( $ j = $ i + 1 ; $ j < $ n && $ j <= $ arr [ $ i ] + $ i ; $ j ++ ) { if ( $ min > $ jumps [ $ j ] ) $ min = $ jumps [ $ j ] ; } if ( $ min != PHP_INT_MAX ) $ jumps [ $ i ] = $ min + 1 ; else $ jumps [ $ i ] = $ min ; } } return $ jumps [ 0 ] ; } $ arr = array ( 1 , 3 , 6 , 1 , 0 , 9 ) ; $ size = sizeof ( $ arr ) ; echo " Minimum ▁ number ▁ of ▁ jumps ▁ to ▁ reach " , " ▁ end ▁ is ▁ " , minJumps ( $ arr , $ size ) ; ? >