Minimum number of Fibonacci jumps to reach end | A Dynamic Programming based Python3 program to find minimum number of jumps to reach Destination ; Function that returns the min number of jump to reach the destination ; We consider only those Fibonacci numbers which are less than n , where we can consider fib [ 30 ] to be the upper bound as this will cross 10 ^ 5 ; DP [ i ] will be storing the minimum number of jumps required for the position i . So DP [ N + 1 ] will have the result we consider 0 as source and N + 1 as the destination ; Base case ( Steps to reach source is ) ; Initialize all table values as Infinite ; Go through each positions till destination . ; Calculate the minimum of that position if all the Fibonacci numbers are considered ; If the position is safe or the position is the destination then only we calculate the minimum otherwise the cost is MAX as default ; - 1 denotes if there is no path possible ; Driver Code
MAX = 1e9 NEW_LINE def minJumps ( arr , N ) : NEW_LINE INDENT fib = [ 0 for i in range ( 30 ) ] NEW_LINE fib [ 0 ] = 0 NEW_LINE fib [ 1 ] = 1 NEW_LINE for i in range ( 2 , 30 ) : NEW_LINE INDENT fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] NEW_LINE DEDENT DP = [ 0 for i in range ( N + 2 ) ] NEW_LINE DP [ 0 ] = 0 NEW_LINE for i in range ( 1 , N + 2 ) : NEW_LINE INDENT DP [ i ] = MAX NEW_LINE DEDENT for i in range ( 1 , N + 2 ) : NEW_LINE INDENT for j in range ( 1 , 30 ) : NEW_LINE INDENT if ( ( arr [ i - 1 ] == 1 or i == N + 1 ) and i - fib [ j ] >= 0 ) : NEW_LINE INDENT DP [ i ] = min ( DP [ i ] , 1 + DP [ i - fib [ j ] ] ) NEW_LINE DEDENT DEDENT DEDENT if ( DP [ N + 1 ] != MAX ) : NEW_LINE INDENT return DP [ N + 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT arr = [ 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minJumps ( arr , n - 1 ) ) NEW_LINE