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

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)

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.

```
#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;
```
```
}
```

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

 
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

« Prev - Subset Sum Problem using Dynamic Programming

» Next - Count Number of Ways to Reach a Given Score Problem

Related Posts:

Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Check Computer Science Books
Practice Programming MCQs

Recommended Articles: