Minimum number of Fibonacci jumps to reach end

0 0 9 minutes read

Given an array of 0s and 1s, If any particular index i has value 1 then it is a safe index and if the value is 0 then it is an unsafe index. A man is standing at index -1(source) can only land on a safe index and he has to reach the Nth index (last position). At each jump, the man can only travel a distance equal to any Fibonacci Number. You have to minimize the number of steps, provided man can jump only in forward direction.
Note: First few Fibonacci numbers are – 0, 1, 1, 2, 3, 5, 8, 13, 21….
Examples:

Input: arr[]= {0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0}
Output: 3
The person will jump from:
1) index -1 to index 4 (a distance of jump = 5)
2) index 4 to index 6 (a distance of jump = 2)
3) index 6 to the destination (a distance of jump = 5)
Input: arr[]= {0, 0}
Output: 1
The person will jump from:
1) index -1 to destination (a distance of jump = 3)

Approach:

First, we will create an array fib[] for storing fibonacci numbers.
Then, we will create a DP array and initialize it with INT_MAX and the 0th index DP[0] = 0 and will move in the same way as Coin Change Problem with minimum number of coins.

The DP definition and recurrence is as followed:

 
 DP[i] = min( DP[i], 1 + DP[i-fib[j]] )

where i is the current index and j denotes
the jth fibonacci number of which the
jump is possible

Here DP[i] denotes the minimum steps required to reach index i considering all Fibonacci numbers.

Below is the implementation of the approach:

C++

// A Dynamic Programming based 
// C++ program to find minimum 
// number of jumps to reach 
// Destination 
#include <bits/stdc++.h> 
using namespace std; 
#define MAX 1e9 
  
// Function that returns the min 
// number of jump to reach the 
// destination 
int minJumps(int arr[], int N) 
{ 
    // 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 
    int fib[30]; 
    fib[0] = 0; 
    fib[1] = 1; 
    for (int i = 2; i < 30; i++) 
        fib[i] = fib[i - 1] + fib[i - 2]; 
  
    // 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 
    int DP[N + 2]; 
  
    // Base case (Steps to reach source is) 
    DP[0] = 0; 
  
    // Initialize all table values as Infinite 
    for (int i = 1; i <= N + 1; i++) 
        DP[i] = MAX; 
  
    // Compute minimum jumps required 
    // considering each Fibonacci 
    // numbers one by one. 
  
    // Go through each positions 
    // till destination. 
    for (int i = 1; i <= N + 1; i++) { 
  
        // Calculate the minimum of that 
        // position if all the Fibonacci 
        // numbers are considered 
        for (int j = 1; j < 30; j++) { 
  
            // If the position is safe 
            // or the position is the 
            // destination then only we 
            // calculate the minimum 
            // otherwise the cost is 
            // MAX as default 
            if ((arr[i - 1] == 1 
                 || i == N + 1) 
                && i - fib[j] >= 0) 
                DP[i] = min(DP[i], 
                            1 + DP[i - fib[j]]); 
        } 
    } 
  
    // -1 denotes if there is 
    // no path possible 
    if (DP[N + 1] != MAX) 
        return DP[N + 1]; 
    else
        return -1; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int arr[] = { 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << minJumps(arr, n); 
    return 0; 
} 

Java

// A Dynamic Programming based  
// Java program to find minimum  
// number of jumps to reach  
// Destination 
import java.util.*;  
import java.lang.*;  
  
class GFG  
{ 
      
// Function that returns the min  
// number of jump to reach the  
// destination 
public static int minJumps(int arr[], int N)  
{ 
    int MAX = 1000000; 
      
    // 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  
    int[] fib = new int[30];  
    fib[0] = 0;  
    fib[1] = 1; 
      
    for (int i = 2; i < 30; i++)  
    fib[i] = fib[i - 1] + fib[i - 2];  
      
    // 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  
    int[] DP = new int[N + 2];  
      
    // Base case (Steps to reach source is)  
    DP[0] = 0;  
  
    // Initialize all table values as Infinite  
    for (int i = 1; i <= N + 1; i++)  
        DP[i] = MAX;  
  
    // Compute minimum jumps required  
    // considering each Fibonacci  
    // numbers one by one.  
  
    // Go through each positions  
    // till destination.  
    for (int i = 1; i <= N + 1; i++) 
    {  
  
        // Calculate the minimum of that  
        // position if all the Fibonacci  
        // numbers are considered  
        for (int j = 1; j < 30; j++)  
        {  
  
            // If the position is safe  
            // or the position is the  
            // destination then only we  
            // calculate the minimum  
            // otherwise the cost is  
            // MAX as default  
            if ((i == N + 1 ||  
                 arr[i - 1] == 1) && 
                 i - fib[j] >= 0)  
                DP[i] = Math.min(DP[i], 1 + 
                                 DP[i - fib[j]]);  
        }  
    }  
  
    // -1 denotes if there is  
    // no path possible  
    if (DP[N + 1] != MAX)  
        return DP[N + 1];  
    else
        return -1;  
}  
  
// Driver Code  
public static void main (String[] args)  
{  
    int[] arr = new int[]{ 0, 0, 0, 1, 1, 0, 
                              1, 0, 0, 0, 0 };  
    int n = 11;  
    int ans = minJumps(arr, n);  
    System.out.println(ans);  
} 
} 
  
// This code is contributed by Mehul 

Python3

# A Dynamic Programming based Python3 program  
# to find minimum number of jumps to reach 
# Destination 
MAX = 1e9
  
# Function that returns the min number  
# of jump to reach the destination 
def minJumps(arr, N): 
      
    # 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 
    fib = [0 for i in range(30)] 
    fib[0] = 0
    fib[1] = 1
    for i in range(2, 30): 
        fib[i] = fib[i - 1] + fib[i - 2] 
  
    # 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 
    DP = [0 for i in range(N + 2)] 
  
    # Base case (Steps to reach source is) 
    DP[0] = 0
  
    # Initialize all table values as Infinite 
    for i in range(1, N + 2): 
        DP[i] = MAX
  
    # Compute minimum jumps required 
    # considering each Fibonacci 
    # numbers one by one. 
  
    # Go through each positions 
    # till destination. 
    for i in range(1, N + 2): 
  
        # Calculate the minimum of that 
        # position if all the Fibonacci 
        # numbers are considered 
        for j in range(1, 30): 
  
            # If the position is safe or the  
            # position is the destination then  
            # only we calculate the minimum 
            # otherwise the cost is MAX as default 
            if ((arr[i - 1] == 1 or i == N + 1) and 
                                    i - fib[j] >= 0): 
                DP[i] = min(DP[i], 1 + DP[i - fib[j]]) 
  
    # -1 denotes if there is 
    # no path possible 
    if (DP[N + 1] != MAX): 
        return DP[N + 1] 
    else: 
        return -1
  
# Driver Code 
arr = [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0] 
n = len(arr) 
  
print(minJumps(arr, n - 1)) 
  
# This code is contributed by Mohit Kumar 

C#

// A Dynamic Programming based  
// C# program to find minimum  
// number of jumps to reach  
// Destination 
using System; 
using System.Collections.Generic; 
  
class GFG  
{ 
      
// Function that returns the min  
// number of jump to reach the  
// destination 
public static int minJumps(int []arr, int N)  
{ 
    int MAX = 1000000; 
      
    // 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  
    int[] fib = new int[30];  
    fib[0] = 0;  
    fib[1] = 1; 
      
    for (int i = 2; i < 30; i++)  
    fib[i] = fib[i - 1] + fib[i - 2];  
      
    // 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  
    int[] DP = new int[N + 2];  
      
    // Base case (Steps to reach source is)  
    DP[0] = 0;  
  
    // Initialize all table values as Infinite  
    for (int i = 1; i <= N + 1; i++)  
        DP[i] = MAX;  
  
    // Compute minimum jumps required  
    // considering each Fibonacci  
    // numbers one by one.  
  
    // Go through each positions  
    // till destination.  
    for (int i = 1; i <= N + 1; i++) 
    {  
  
        // Calculate the minimum of that  
        // position if all the Fibonacci  
        // numbers are considered  
        for (int j = 1; j < 30; j++)  
        {  
  
            // If the position is safe  
            // or the position is the  
            // destination then only we  
            // calculate the minimum  
            // otherwise the cost is  
            // MAX as default  
            if ((i == N + 1 ||  
                arr[i - 1] == 1) && 
                i - fib[j] >= 0)  
                DP[i] = Math.Min(DP[i], 1 + 
                                 DP[i - fib[j]]);  
        }  
    }  
  
    // -1 denotes if there is  
    // no path possible  
    if (DP[N + 1] != MAX)  
        return DP[N + 1];  
    else
        return -1;  
}  
  
// Driver Code  
public static void Main (String[] args)  
{  
    int[] arr = new int[]{ 0, 0, 0, 1, 1, 0, 
                              1, 0, 0, 0, 0 };  
    int n = 11;  
    int ans = minJumps(arr, n);  
    Console.WriteLine(ans);  
} 
} 
  
// This code is contributed by Princi Singh 

Javascript

<script> 
  
// A Dynamic Programming based 
// Javascript program to find minimum 
// number of jumps to reach 
// Destination 
  
const MAX = 1000000000; 
  
// Function that returns the min 
// number of jump to reach the 
// destination 
function minJumps(arr, N) 
{ 
    // 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 
    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]; 
  
    // 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 
    let DP = new Array(N + 2); 
  
    // Base case (Steps to reach source is) 
    DP[0] = 0; 
  
    // Initialize all table values as Infinite 
    for (let i = 1; i <= N + 1; i++) 
        DP[i] = MAX; 
  
    // Compute minimum jumps required 
    // considering each Fibonacci 
    // numbers one by one. 
  
    // Go through each positions 
    // till destination. 
    for (let i = 1; i <= N + 1; i++) { 
  
        // Calculate the minimum of that 
        // position if all the Fibonacci 
        // numbers are considered 
        for (let j = 1; j < 30; j++) { 
  
            // If the position is safe 
            // or the position is the 
            // destination then only we 
            // calculate the minimum 
            // otherwise the cost is 
            // MAX as default 
            if ((arr[i - 1] == 1 
                 || i == N + 1) 
                && i - fib[j] >= 0) 
                DP[i] = Math.min(DP[i], 
                            1 + DP[i - fib[j]]); 
        } 
    } 
  
    // -1 denotes if there is 
    // no path possible 
    if (DP[N + 1] != MAX) 
        return DP[N + 1]; 
    else
        return -1; 
} 
  
// Driver program to test above function 
    let arr = [ 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0 ]; 
    let n = arr.length; 
  
    document.write(minJumps(arr, n)); 
  
</script>

Output:

Time Complexity: $O(Nlog(N))$

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!