This is a C++ Program that Solves Minimum Number of Jumps Problem using Dynamic Programming technique.
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.
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.
Case-1:
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)
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.
#include<iostream>
#include<climits>
using namespace std;
int minJumps(int n, int jumps[])
{
int i, j;
int dp[n];
dp[0]=0;
//initialize with infinity
for(i=1;i<n;i++)
dp[i]=INT_MAX;
for(i=0;i<n-1;i++)
{
for(j=1;j<=jumps[i] && i+j<n;j++)
{
dp[i+j]=min(dp[i+j],1+dp[i]);
}
}
return dp[n-1];
}
int main()
{
int i,j;
int n;
cout<<"Enter the total number of steps"<<endl;
cin>>n;
int jumps[n];
cout<<"Enter the max jump values for each step"<<endl;
for(i=0;i<n;i++)
cin>>jumps[i];
cout<<"Minimum number of jumps required to reach end is "<<endl;
cout<<minJumps(n, jumps);
cout<<endl;
return 0;
}
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.
Case-1: $ g++ min_jumps.cpp $ ./a.out Enter the total number of steps 10 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 2
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
- Check Computer Science Books
- Practice Programming MCQs