C program to find the minimum number of hops to reach the end

Given an array of non-negative integers, representing the maximum number Steps that can be taken forward from this element. The pointer is initially located at the first index [0 index] of the array. Your goal is to reach the end The index into the array in the minimum number of steps. if unreachable end of the array, then print the largest integer.

The naive approach is to start with the initial {main} component and recursively call all components accessible from the first element. The minimum jump range from the first to the end is calculated using the minimum jump range required to reach the end from the first accessible element.

minJumps(start, end) = Min ( minJumps(k, end) )
for all k accessible from the start

Here, we will use the top-down dynamic programming approach. We will use a Hashmap to store subproblem results and whenever we create a solution, first check if the subproblem has been solved and if so use it.

Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}

Explanation

The first element is 1, so it can only go to 2. The second element is 2, so you can go up to 2 steps, e.g. to 4 or 1. from reach 1 to 4, and So on and so forth.

Complexity of dynamic programming methods for finding minimum numbers The number of jumps to reach the end of the array is O(n^2), and the space complexity is O(n)

Example

Real-time demonstration

#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
   int steps[n];
   int i, j;
   if (n == 0 || arr[0] == 0)
      return INT_MAX;
   steps[0] = 0;
   for (i = 1; i < n; i++){
      steps[i] = INT_MAX;
      for (j = 0; j < i; j++){
         if (i <= j + arr[j] && steps[j] != INT_MAX){
            steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
            break;
         }
      }
   }
   return steps[n - 1];
}
int main (){
   int arr[100];
   int n;
   printf ("Enter size of the array:");
   scanf ("%d", &n);
   printf ("Enter elements in the array:");
   for (int i = 0; i < n; i++){
      scanf ("%d", &arr[i]);
   }
   printf ("Minimum number of steps : %d", min_steps (arr, n));
   return 0;
}

Output

Enter size of array : 7
Enter elements in the array :2 1 1 5 2 1 1
Minimum number of steps : 3

The above is the detailed content of C program to find the minimum number of hops to reach the end. For more information, please follow other related articles on the PHP Chinese website!