Careful observation reveals that the preceding recursive solution possesses the two following Dynamic Programming characteristics:
Number of ways to reach the array end from current index i, i.e., minJumps(i), depends on the optimal solutions of the subproblems minJumps(i+1), minJumps(i+2), …., minJumps(i+arr[i]). Finding the minimum leaps in these ideal substructures will help us to quickly determine the overall count of jumps needed to reach the end.
As we use a recursive method in this problem, we observe that some subproblems are computed several times. Thus, we may find the value for a certain index and save it in an array such that, should this index be requested once more, we can just return the saved value.
Use the ideas below to carry them out:
Make memo[] such that, from memo[i], memo[i] denotes the lowest number of leaps required to reach memo[n-1] thereby storing previously solved subproblems.
If the same state is called more than once throughout the recursion call, we can straightly return the response kept for that state instead of computing once again.
Otherwise, in every recursive operation, acquire all the reachable nodes from that index.
Recursive the function for every index call.
From current index, determine the lowest number of jumps needed to reach the end.
C++
// c++ program to find the minimum number
// of jumps to reach the end of the array
#include <bits/stdc++.h>
using namespace std;
int minJumpsRecur(int i, vector<int> &arr, vector<int> &memo) {
// Return 0 when last element is reached.
if (i == arr.size()-1)
return 0;
// If value for current index is memoized,
// then return it.
if (memo[i] != -1) return memo[i];
// Traverse through all the points
// reachable from arr[i].
// Recursively, get the minimum number
// of jumps needed to reach array end from
// these points.
int ans = INT_MAX;
for (int j=i+1; j<=i+arr[i] && j<arr.size(); j++) {
int val = minJumpsRecur(j, arr, memo);
if (val != INT_MAX)
ans = min(ans, 1+val);
}
// Memoize the value and
// return it.
return memo[i] = ans;
}
// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
int minJumps(vector<int>& arr) {
// array to memoize values
vector<int> memo(arr.size(), -1);
int ans = minJumpsRecur(0, arr, memo);
// If end cannot be reached.
if (ans == INT_MAX)
return -1;
return ans;
}
int main() {
vector<int> arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
cout << minJumps(arr);
return 0;
}Java
// Java program to find the minimum number
// of jumps to reach the end of the array
class GfG {
static int minJumpsRecur(int i, int[] arr, int[] memo) {
// Return 0 when last element is reached.
if (i == arr.length - 1)
return 0;
// If value for current index is memoized,
// then return it.
if (memo[i] != -1) return memo[i];
// Traverse through all the points
// reachable from arr[i].
// Recursively, get the minimum number
// of jumps needed to reach array end from
// these points.
int ans = Integer.MAX_VALUE;
for (int j = i + 1; j <= i + arr[i] && j < arr.length; j++) {
int val = minJumpsRecur(j, arr, memo);
if (val != Integer.MAX_VALUE)
ans = Math.min(ans, 1 + val);
}
// Memoize the value and
// return it.
return memo[i] = ans;
}
// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
static int minJumps(int[] arr) {
// array to memoize values
int[] memo = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
memo[i] = -1;
}
int ans = minJumpsRecur(0, arr, memo);
// If end cannot be reached.
if (ans == Integer.MAX_VALUE)
return -1;
return ans;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
System.out.println(minJumps(arr));
}
}Python
# Python program to find the minimum number
# of jumps to reach the end of the array
def minJumpsRecur(i, arr, memo):
# Return 0 when last element is reached.
if i == len(arr) - 1:
return 0
# If value for current index is memoized,
# then return it.
if memo[i] != -1:
return memo[i]
# Traverse through all the points
# reachable from arr[i].
# Recursively, get the minimum number
# of jumps needed to reach array end from
# these points.
ans = float('inf')
for j in range(i + 1, min(i + arr[i] + 1, len(arr))):
val = minJumpsRecur(j, arr, memo)
if val != float('inf'):
ans = min(ans, 1 + val)
# Memoize the value and
# return it.
memo[i] = ans
return ans
# Function to return the minimum number
# of jumps to reach arr[h] from arr[l]
def minJumps(arr):
# array to memoize values
memo = [-1] * len(arr)
ans = minJumpsRecur(0, arr, memo)
# If end cannot be reached.
if ans == float('inf'):
return -1
return ans
if __name__ == "__main__":
arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
print(minJumps(arr))C#
// C# program to find the minimum number
// of jumps to reach the end of the array
using System;
class GfG {
static int minJumpsRecur(int i, int[] arr, int[] memo) {
// Return 0 when last element is reached.
if (i == arr.Length - 1)
return 0;
// If value for current index is memoized,
// then return it.
if (memo[i] != -1) return memo[i];
// Traverse through all the points
// reachable from arr[i].
// Recursively, get the minimum number
// of jumps needed to reach array end from
// these points.
int ans = int.MaxValue;
for (int j = i + 1; j <= i + arr[i] && j < arr.Length; j++) {
int val = minJumpsRecur(j, arr, memo);
if (val != int.MaxValue)
ans = Math.Min(ans, 1 + val);
}
// Memoize the value and
// return it.
return memo[i] = ans;
}
// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
static int minJumps(int[] arr) {
// array to memoize values
int[] memo = new int[arr.Length];
for (int i = 0; i < arr.Length; i++) {
memo[i] = -1;
}
int ans = minJumpsRecur(0, arr, memo);
// If end cannot be reached.
if (ans == int.MaxValue)
return -1;
return ans;
}
static void Main(string[] args) {
int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
Console.WriteLine(minJumps(arr));
}
}JavaScript
// JavaScript program to find the minimum number
// of jumps to reach the end of the array
function minJumpsRecur(i, arr, memo) {
// Return 0 when last element is reached.
if (i === arr.length - 1)
return 0;
// If value for current index is memoized,
// then return it.
if (memo[i] !== -1) return memo[i];
// Traverse through all the points
// reachable from arr[i].
// Recursively, get the minimum number
// of jumps needed to reach array end from
// these points.
let ans = Infinity;
for (let j = i + 1; j <= i + arr[i] && j < arr.length; j++) {
let val = minJumpsRecur(j, arr, memo);
if (val !== Infinity)
ans = Math.min(ans, 1 + val);
}
// Memoize the value and
// return it.
memo[i] = ans;
return ans;
}
// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
function minJumps(arr) {
// array to memoize values
let memo = new Array(arr.length).fill(-1);
let ans = minJumpsRecur(0, arr, memo);
// If end cannot be reached.
if (ans === Infinity)
return -1;
return ans;
}
let arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
console.log(minJumps(arr));