Minimum Number of Jumps Problem – Dynamic Programming Solutions


This is a C++ Program that Solves Minimum Number of Jumps Problem using Dynamic Programming technique.

Problem Description

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a program to find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Problem Solution

We will progressively calculate the minimum number of jumps required to reach at sttep 1, then at step 2 and finally to reach end. Everytime when we calculate the minimum no. of jumps value for a step, we will use this value to calculate the desired value for further steps.

Expected Input and Output


jump values=2 8 3 6 9 3 0 0 1 3
Minimum number of jumps required to reach end is 2 (2->8->3)
Program/Source Code

Here is source code of the C++ Program to Solve Minimum Number of Jumps Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
  1. #include<iostream>
  2. #include<climits>
  3. using namespace std;
  5. int minJumps(int n, int jumps[])
  6. {
  7.     int i, j;
  8.     int dp[n];
  9.     dp[0]=0;
  11.     //initialize with infinity
  12.     for(i=1;i<n;i++)
  13.         dp[i]=INT_MAX;
  15.     for(i=0;i<n-1;i++)
  16.     {
  17.         for(j=1;j<=jumps[i] && i+j<n;j++)
  18.         {
  19.             dp[i+j]=min(dp[i+j],1+dp[i]);
  20.         }
  21.     }
  23.     return dp[n-1];
  24. }
  26. int main()
  27. {
  28.     int i,j;
  29.     int n;
  31.     cout<<"Enter the total number of steps"<<endl;
  32.     cin>>n;
  34.     int jumps[n];
  36.     cout<<"Enter the max jump values for each step"<<endl;
  37.     for(i=0;i<n;i++)
  38.         cin>>jumps[i];
  40.     cout<<"Minimum number of jumps required to reach end is "<<endl;
  41.     cout<<minJumps(n, jumps);
  43.     cout<<endl;
  44.     return 0;
  45. }
Program Explanation

In the main function, we ask the user to input for the number of steps and the jump values for each step. We pass this value to the function minJumps as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases
$ g++ min_jumps.cpp
$ ./a.out
Enter the total number of steps
Enter the max jump values for each step
2 8 3 6 9 3 0 0 1 3
Minimum number of jumps required to reach end is 

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.