Minimum number of Fibonacci jumps to reach end | A Dynamic Programming based Javascript 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 program to test above function
const MAX = 1000000000 ; function minJumps ( arr , N ) { let fib = new Array ( 30 ) ; fib [ 0 ] = 0 ; fib [ 1 ] = 1 ; for ( let i = 2 ; i < 30 ; i ++ ) fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] ; let DP = new Array ( N + 2 ) ; DP [ 0 ] = 0 ; for ( let i = 1 ; i <= N + 1 ; i ++ ) DP [ i ] = MAX ; for ( let i = 1 ; i <= N + 1 ; i ++ ) { for ( let j = 1 ; j < 30 ; j ++ ) { if ( ( arr [ i - 1 ] == 1 i == N + 1 ) && i - fib [ j ] >= 0 ) DP [ i ] = Math . min ( DP [ i ] , 1 + DP [ i - fib [ j ] ] ) ; } } if ( DP [ N + 1 ] != MAX ) return DP [ N + 1 ] ; else return - 1 ; } let arr = [ 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 ] ; let n = arr . length ; document . write ( minJumps ( arr , n ) ) ;