# Minimum jumps required using Dynamic programming (DP)

Given an array of integers of length N in which value of each index represent maximum jump u can take from that index. You have to **find minimum jumps required** to reach from 0th index to the end of the array(last index).

Submitted by Ritik Aggarwal, on December 17, 2018

**Problem:** You are given an array of integers of length N in which value of each index represents maximum jump u can take from that index. You have to find minimum jumps required to reach from 0th index to the end of the array(last index).

**Constraints:**

1 <= N <= 30,000 0 <= A[i] <= 100

Sample Input 1: 6 2 2 3 1 0 3 Sample Output 1: minimum jumps required is 2 Sample Input 2: 11 1 3 5 8 9 2 6 7 6 8 9 Sample Output 2: minimum jumps required is 3

**Explanation of the problem:**

**For the sample Input1,**

We can jump from **0 ^{th}** index to

**2**index then to last index. So,

^{nd}**2**jumps required.

**For the sample input2,**

We can jump from **0 ^{th}** index to

**1**index then

^{st}**3**index and then last index. So,

^{rd}**3**jumps required.

**Solution: For sample input – 1**

**STATUS OF DP MATRIX AFTER i**

^{th}ITERATION**Note:** Since, we have to take minimum of all the possible jumps so if there are no jumps possible that is arr[i] = 0 then cell will get initialize to non- updated minimum value that is 1000000(denotes infinite steps). Due to presence of 1000001 at 4th index 3rd index also gets this value though arr[3] is non-zero.

**Algorithm:**

**STEP-1:**Create a 1D dp matrix in which**i**cell represent minimum jumps required from^{th}**i**index to the last.^{th}**STEP-2:**Initialize the last index of dp matrix to be zero as it is the end of the array.**STEP-3:**Start filling the dp matrix from second last index.**STEP-4:**From**i**index we can jump maximum of arr[i] value so taking minimum of dp[i + j] where^{th}**j**is ranging from 1 to arr[i] and i + j must be less than length of dp matrix.**STEP-5:**Add 1 to the answer got from step 4(1 jump is required from ith to i+j index) and store the answer at**i**index of dp matrix.^{th}**STEP-6:**return the answer of**0**index of dp matrix.^{th}

**The time complexity of the above code is O(N^2).**

**C++ Implementation **

#include <iostream> using namespace std; int minJumps(int arr[], int n){ int dp[n] = {0}; // if already at last index the number of steps is 0 dp[n-1] = 0; // filling from second last index for(int i = n - 2;i>=0;i--){ int min = 1000000; // value at an index of arr donates maximum_possible jump int jumps_range = arr[i]; // i + j < n is used to avoid jumping out of array length // && also jump can vary from 1 to value of arr at that index for(int j = 1;j<=jumps_range && i + j < n;j++){ // taking minimum of all possible jumps as ith index of // dp matrix represent minmum jumps required to reach from ith // index to the end if(min > dp[i+j]){ min = dp[i+j]; } } // also have to add 1 as 1 jump is required to jump on any // index in jump_range and storing that value dp[i] = 1 + min; } // return the minimum jumps from 0th index to the end return dp[0]; } // driver function to check the code int main() { int n; cout<<"Enter size of the array: "; cin >> n; int arr[n] = {0}; cout<<"Enter array elements: "; for(int j = 0;j<n;j++){ cin >> arr[j]; } for(int val : arr){ cout << val << " "; } cout <<"\nminimum jumps required is "<< minJumps(arr, n) << endl; return 0; }

**Output**

Enter size of the array: 6 Enter array elements: 2 2 3 1 0 3 2 2 3 1 0 3 minimum jumps required is 2

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!