Minimum number of jumps to reach end | Returns Minimum number of jumps to reach end ; jumps [ 0 ] will hold the result ; 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 ] form arr [ i ] ; If arr [ i ] is 0 then arr [ n - 1 ] can 't be reached from here ; If we can directly 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 reachavle points and takes the minimum ; Handle overflow ; or INT_MAX ; Driver program to test above function
def minJumps ( arr , n ) : NEW_LINE INDENT jumps = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( arr [ i ] == 0 ) : NEW_LINE INDENT jumps [ i ] = float ( ' inf ' ) NEW_LINE DEDENT elif ( arr [ i ] >= n - i - 1 ) : NEW_LINE INDENT jumps [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT min = float ( ' inf ' ) NEW_LINE for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( j <= arr [ i ] + i ) : NEW_LINE INDENT if ( min > jumps [ j ] ) : NEW_LINE INDENT min = jumps [ j ] NEW_LINE DEDENT DEDENT DEDENT if ( min != float ( ' inf ' ) ) : NEW_LINE INDENT jumps [ i ] = min + 1 NEW_LINE DEDENT else : NEW_LINE INDENT jumps [ i ] = min NEW_LINE DEDENT DEDENT DEDENT return jumps [ 0 ] NEW_LINE DEDENT arr = [ 1 , 3 , 6 , 3 , 2 , 3 , 6 , 8 , 9 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( ' Minimum ▁ number ▁ of ▁ jumps ▁ to ▁ reach ' , ' end ▁ is ' , minJumps ( arr , n - 1 ) ) NEW_LINE