Dada una array de enteros donde cada elemento representa el número máximo de pasos que se pueden realizar desde ese elemento. Escriba una función para devolver el número mínimo de saltos para llegar al final de la array (a partir del primer elemento). Si un elemento es 0, no pueden moverse a través de ese elemento. Si no se puede alcanzar el final, devuelve -1.
Ejemplos:
Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 9 -> 9)
Explanation: Jump from 1st element
to 2nd element as there is only 1 step,
now there are three options 5, 8 or 9.
If 8 or 9 is chosen then the end node 9
can be reached. So 3 jumps are made.
Input: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 10
Explanation: In every step a jump
is needed so the count of jumps is 10.
El primer elemento es 1, por lo que solo puede ir a 3. El segundo elemento es 3, por lo que puede hacer como máximo 3 pasos, por ejemplo, a 5 u 8 o 9.
Método 1 : enfoque recursivo ingenuo.
Enfoque: un enfoque ingenuo es comenzar desde el primer elemento y llamar recursivamente a todos los elementos accesibles desde el primer elemento. El número mínimo de saltos para llegar al final desde el primero se puede calcular usando el número mínimo de saltos necesarios para llegar al final desde los elementos alcanzables desde el primero.
minJumps(start, end) = Min ( minJumps(k, end) ) para todos los k accesibles desde el inicio
C++
// C++ program to find Minimum
// number of jumps to reach end
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
int minJumps(int arr[], int n)
{
// Base case: when source and
// destination are same
if (n == 1)
return 0;
// Traverse through all the points
// reachable from arr[l]
// Recursively, get the minimum number
// of jumps needed to reach arr[h] from
// these reachable points
int res = INT_MAX;
for (int i = n - 2; i >= 0; i--) {
if (i + arr[i] >= n - 1) {
int sub_res = minJumps(arr, i + 1);
if (sub_res != INT_MAX)
res = min(res, sub_res + 1);
}
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 6, 3, 2,
3, 6, 8, 9, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum number of jumps to";
cout << " reach the end is " << minJumps(arr, n);
return 0;
}
// This code is contributed
// by Shivi_Aggarwal
C
// C program to find Minimum
// number of jumps to reach end
#include <limits.h>
#include <stdio.h>
// Returns minimum number of
// jumps to reach arr[h] from arr[l]
int minJumps(int arr[], int l, int h)
{
// Base case: when source and destination are same
if (h == l)
return 0;
// When nothing is reachable from the given source
if (arr[l] == 0)
return INT_MAX;
// Traverse through all the points
// reachable from arr[l]. Recursively
// get the minimum number of jumps
// needed to reach arr[h] from these
// reachable points.
int min = INT_MAX;
for (int i = l + 1; i <= h && i <= l + arr[l]; i++) {
int jumps = minJumps(arr, i, h);
if (jumps != INT_MAX && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
printf(
"Minimum number of jumps to reach end is %d ",
minJumps(arr, 0, n - 1));
return 0;
}
Java
// Java program to find Minimum
// number of jumps to reach end
import java.util.*;
import java.io.*;
class GFG {
// Returns minimum number of
// jumps to reach arr[h] from arr[l]
static int minJumps(int arr[], int l, int h)
{
// Base case: when source
// and destination are same
if (h == l)
return 0;
// When nothing is reachable
// from the given source
if (arr[l] == 0)
return Integer.MAX_VALUE;
// Traverse through all the points
// reachable from arr[l]. Recursively
// get the minimum number of jumps
// needed to reach arr[h] from these
// reachable points.
int min = Integer.MAX_VALUE;
for (int i = l + 1; i <= h
&& i <= l + arr[l];
i++) {
int jumps = minJumps(arr, i, h);
if (jumps != Integer.MAX_VALUE && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
int n = arr.length;
System.out.print("Minimum number of jumps to reach end is "
+ minJumps(arr, 0, n - 1));
}
}
// This code is contributed by Sahil_Bansall
Python3
# Python3 program to find Minimum
# number of jumps to reach end
# Returns minimum number of jumps
# to reach arr[h] from arr[l]
def minJumps(arr, l, h):
# Base case: when source and
# destination are same
if (h == l):
return 0
# when nothing is reachable
# from the given source
if (arr[l] == 0):
return float('inf')
# Traverse through all the points
# reachable from arr[l]. Recursively
# get the minimum number of jumps
# needed to reach arr[h] from
# these reachable points.
min = float('inf')
for i in range(l + 1, h + 1):
if (i < l + arr[l] + 1):
jumps = minJumps(arr, i, h)
if (jumps != float('inf') and
jumps + 1 < min):
min = jumps + 1
return min
# Driver program to test above function
arr = [1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
n = len(arr)
print('Minimum number of jumps to reach',
'end is', minJumps(arr, 0, n-1))
# This code is contributed by Soumen Ghosh
C#
// C# program to find Minimum
// number of jumps to reach end
using System;
class GFG {
// Returns minimum number of
// jumps to reach arr[h] from arr[l]
static int minJumps(int[] arr, int l, int h)
{
// Base case: when source
// and destination are same
if (h == l)
return 0;
// When nothing is reachable
// from the given source
if (arr[l] == 0)
return int.MaxValue;
// Traverse through all the points
// reachable from arr[l]. Recursively
// get the minimum number of jumps
// needed to reach arr[h] from these
// reachable points.
int min = int.MaxValue;
for (int i = l + 1; i <= h && i <= l + arr[l]; i++) {
int jumps = minJumps(arr, i, h);
if (jumps != int.MaxValue && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
int n = arr.Length;
Console.Write("Minimum number of jumps to reach end is "
+ minJumps(arr, 0, n - 1));
}
}
// This code is contributed by Sam007
PHP
<?php
// php program to find Minimum
// number of jumps to reach end
// Returns minimum number of jumps
// to reach arr[h] from arr[l]
function minJumps($arr, $l, $h)
{
// Base case: when source and
// destination are same
if ($h == $l)
return 0;
// When nothing is reachable
// from the given source
if ($arr[$l] == 0)
return INT_MAX;
// Traverse through all the points
// reachable from arr[l]. Recursively
// get the minimum number of jumps
// needed to reach arr[h] from these
// reachable points.
$min = 999999;
for ($i = $l+1; $i <= $h &&
$i <= $l + $arr[$l]; $i++)
{
$jumps = minJumps($arr, $i, $h);
if($jumps != 999999 &&
$jumps + 1 < $min)
$min = $jumps + 1;
}
return $min;
}
// Driver program to test above function
$arr = array(1, 3, 6, 3, 2, 3, 6, 8, 9, 5);
$n = count($arr);
echo "Minimum number of jumps to reach "
. "end is ". minJumps($arr, 0, $n-1);
// This code is contributed by Sam007
?>
Javascript
<script>
// JavaScript program to find Minimum
// number of jumps to reach end
// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
function minJumps(arr, n)
{
// Base case: when source and
// destination are same
if (n == 1)
return 0;
// Traverse through all the points
// reachable from arr[l]
// Recursively, get the minimum number
// of jumps needed to reach arr[h] from
// these reachable points
let res = Number.MAX_VALUE;
for (let i = n - 2; i >= 0; i--) {
if (i + arr[i] >= n - 1) {
let sub_res = minJumps(arr, i + 1);
if (sub_res != Number.MAX_VALUE)
res = Math.min(res, sub_res + 1);
}
}
return res;
}
// Driver Code
let arr = [ 1, 3, 6, 3, 2,
3, 6, 8, 9, 5 ];
let n = arr.length;
document.write("Minimum number of jumps to");
document.write(" reach end is " + minJumps(arr, n));
</script>
Producción:
Minimum number of jumps to reach end is 4
Análisis de Complejidad:
- Complejidad temporal: O(n^n).
Hay un máximo de n formas posibles de moverse desde un elemento. Entonces, el número máximo de pasos puede ser N ^ N, por lo que el límite superior de la complejidad del tiempo es O (n ^ n) - Espacio Auxiliar: O(1).
No se requiere espacio (si se ignora el espacio de pila recursivo).
Nota: Si se rastrea la ejecución de este método, se puede ver que habrá subproblemas superpuestos. Por ejemplo, minJumps(3, 9) se llamará dos veces ya que se puede acceder a arr[3] desde arr[1] y arr[2]. Entonces este problema tiene ambas propiedades ( subestructura óptima y subproblemas superpuestos ) de Programación Dinámica.
Método 2: Programación Dinámica.
Acercarse:
- De esta forma, haz un array de saltos[] de izquierda a derecha tal que saltos[i] indique el número mínimo de saltos necesarios para llegar a arr[i] desde arr[0].
- Para llenar la array de saltos, ejecute un contador de bucle interno de bucle anidado es j y el contador de bucle externo es i.
- Bucle exterior de 1 a n-1 y bucle interior de 0 a i.
- si i es menor que j + arr[j] entonces establezca jumps[i] al mínimo de jumps[i] y jumps[j] + 1. inicialmente establezca jump[i] a INT MAX
- Finalmente, regresa salta[n-1].
C++
// C++ program for Minimum number
// of jumps to reach end
#include <bits/stdc++.h>
using namespace std;
int min(int x, int y) { return (x < y) ? x : y; }
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
// jumps[n-1] will hold the result
int* jumps = new int[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
jumps[0] = 0;
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++) {
jumps[i] = INT_MAX;
for (j = 0; j < i; j++) {
if (i <= j + arr[j] && jumps[j] != INT_MAX) {
jumps[i] = min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
}
// Driver code
int main()
{
int arr[] = { 1, 3, 6, 1, 0, 9 };
int size = sizeof(arr) / sizeof(int);
cout << "Minimum number of jumps to reach end is "
<< minJumps(arr, size);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program for Minimum number
// of jumps to reach end
#include <limits.h>
#include <stdio.h>
int min(int x, int y) { return (x < y) ? x : y; }
// Returns minimum number of
// jumps to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
// jumps[n-1] will hold the result
int jumps[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
jumps[0] = 0;
// Find the minimum number of
// jumps to reach arr[i]
// from arr[0], and assign this
// value to jumps[i]
for (i = 1; i < n; i++) {
jumps[i] = INT_MAX;
for (j = 0; j < i; j++) {
if (i <= j + arr[j] && jumps[j] != INT_MAX) {
jumps[i] = min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 3, 6, 1, 0, 9 };
int size = sizeof(arr) / sizeof(int);
printf("Minimum number of jumps to reach end is %d ",
minJumps(arr, size));
return 0;
}
Java
// JAVA Code for Minimum number
// of jumps to reach end
class GFG {
private static int minJumps(int[] arr, int n)
{
// jumps[n-1] will hold the
int jumps[] = new int[n];
// result
int i, j;
// if first element is 0,
if (n == 0 || arr[0] == 0)
return Integer.MAX_VALUE;
// end cannot be reached
jumps[0] = 0;
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++) {
jumps[i] = Integer.MAX_VALUE;
for (j = 0; j < i; j++) {
if (i <= j + arr[j]
&& jumps[j]
!= Integer.MAX_VALUE) {
jumps[i] = Math.min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
}
// driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 3, 6, 1, 0, 9 };
System.out.println("Minimum number of jumps to reach end is : "
+ minJumps(arr, arr.length));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to find Minimum
# number of jumps to reach end
# Returns minimum number of jumps
# to reach arr[n-1] from arr[0]
def minJumps(arr, n):
jumps = [0 for i in range(n)]
if (n == 0) or (arr[0] == 0):
return float('inf')
jumps[0] = 0
# Find the minimum number of
# jumps to reach arr[i] from
# arr[0] and assign this
# value to jumps[i]
for i in range(1, n):
jumps[i] = float('inf')
for j in range(i):
if (i <= j + arr[j]) and (jumps[j] != float('inf')):
jumps[i] = min(jumps[i], jumps[j] + 1)
break
return jumps[n-1]
# Driver Program to test above function
arr = [1, 3, 6, 1, 0, 9]
size = len(arr)
print('Minimum number of jumps to reach',
'end is', minJumps(arr, size))
# This code is contributed by Soumen Ghosh
C#
// C# Code for Minimum number of jumps to reach end
using System;
class GFG {
static int minJumps(int[] arr, int n)
{
// jumps[n-1] will hold the
// result
int[] jumps = new int[n];
// if first element is 0,
if (n == 0 || arr[0] == 0)
// end cannot be reached
return int.MaxValue;
jumps[0] = 0;
// Find the minimum number of
// jumps to reach arr[i]
// from arr[0], and assign
// this value to jumps[i]
for (int i = 1; i < n; i++) {
jumps[i] = int.MaxValue;
for (int j = 0; j < i; j++) {
if (i <= j + arr[j] && jumps[j] != int.MaxValue) {
jumps[i] = Math.Min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
}
// Driver program
public static void Main()
{
int[] arr = { 1, 3, 6, 1, 0, 9 };
Console.Write("Minimum number of jumps to reach end is : " + minJumps(arr, arr.Length));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP code for Minimum number of
// jumps to reach end
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
function minJumps($arr, $n)
{
// jumps[n-1] will
// hold the result
$jumps = array($n);
if ($n == 0 || $arr[0] == 0)
return 999999;
$jumps[0] = 0;
// Find the minimum number of
// jumps to reach arr[i]
// from arr[0], and assign
// this value to jumps[i]
for ($i = 1; $i < $n; $i++)
{
$jumps[$i] = 999999;
for ($j = 0; $j < $i; $j++)
{
if ($i <= $j + $arr[$j] &&
$jumps[$j] != 999999)
{
$jumps[$i] = min($jumps[$i],
$jumps[$j] + 1);
break;
}
}
}
return $jumps[$n-1];
}
// Driver Code
$arr = array(1, 3, 6, 1, 0, 9);
$size = count($arr);
echo "Minimum number of jumps to reach end is ".
minJumps($arr, $size);
// This code is contributed by Sam007
?>
Javascript
<script>
// JavaScript Code for Minimum number
// of jumps to reach end
function minJumps(arr , n)
{
// jumps[n-1] will hold the
var jumps = Array.from({length: n}, (_, i) => 0);;
// result
var i, j;
// if first element is 0,
if (n == 0 || arr[0] == 0)
return Number.MAX_VALUE;
// end cannot be reached
jumps[0] = 0;
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++) {
jumps[i] = Number.MAX_VALUE;
for (j = 0; j < i; j++) {
if (i <= j + arr[j]
&& jumps[j]
!= Number.MAX_VALUE) {
jumps[i] = Math.min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
}
// driver program to test above function
var arr = [ 1, 3, 6, 1, 0, 9 ];
document.write("Minimum number of jumps to reach end is : "
+ minJumps(arr, arr.length));
// This code contributed by shikhasingrajput
</script>
Producción:
Minimum number of jumps to reach end is 3
Gracias a paras por sugerir este método.
Complejidad del tiempo: O(n^2)
Espacio Auxiliar: O(n)
Método 3 : Programación Dinámica.
En este método, construimos la array jumps[] de derecha a izquierda, de modo que jumps[i] indica el número mínimo de saltos necesarios para llegar a arr[n-1] desde arr[i]. Finalmente, devolvemos saltos[0].
C++
// C++ program to find Minimum number of jumps to reach end
#include <bits/stdc++.h>
using namespace std;
// Returns Minimum number of jumps to reach end
int minJumps(int arr[], int n)
{
// jumps[0] will hold the result
int* jumps = new int[n];
int min;
// Minimum number of jumps needed to reach last element
// from last elements itself is always 0
jumps[n - 1] = 0;
// Start from the second element, move from right to
// left and construct the jumps[] array where jumps[i]
// represents minimum number of jumps needed to reach
// arr[m-1] from arr[i]
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is 0 then arr[n-1] can't be reached
// from here
if (arr[i] == 0)
jumps[i] = INT_MAX;
// If we can directly reach to the end point from
// here then jumps[i] is 1
else if (arr[i] >= n - i - 1)
jumps[i] = 1;
// Otherwise, to find out the minimum number of
// jumps needed to reach arr[n-1], check all the
// points reachable from here and jumps[] value for
// those points
else {
// initialize min value
min = INT_MAX;
// following loop checks with all reachable
// points and takes the minimum
for (int j = i + 1; j < n && j <= arr[i] + i;
j++) {
if (min > jumps[j])
min = jumps[j];
}
// Handle overflow
if (min != INT_MAX)
jumps[i] = min + 1;
else
jumps[i] = min; // or INT_MAX
}
}
return jumps[0];
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 3, 6, 1, 0, 9 };
int size = sizeof(arr) / sizeof(int);
cout << "Minimum number of jumps to reach"
<< " end is " << minJumps(arr, size);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to find Minimum number of jumps to reach end
#include <limits.h>
#include <stdio.h>
// Returns Minimum number of jumps to reach end
int minJumps(int arr[], int n)
{
// jumps[0] will hold the result
int jumps[n];
int min;
// Minimum number of jumps needed to reach last element
// from last elements itself is always 0
jumps[n - 1] = 0;
// Start from the second element, move from right to
// left and construct the jumps[] array where jumps[i]
// represents minimum number of jumps needed to reach
// arr[m-1] from arr[i]
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is 0 then arr[n-1] can't be reached
// from here
if (arr[i] == 0)
jumps[i] = INT_MAX;
// If we can directly reach to the end point from
// here then jumps[i] is 1
else if (arr[i] >= n - i - 1)
jumps[i] = 1;
// Otherwise, to find out the minimum number of
// jumps needed to reach arr[n-1], check all the
// points reachable from here and jumps[] value for
// those points
else {
// initialize min value
min = INT_MAX;
// following loop checks with all reachable
// points and takes the minimum
for (int j = i + 1; j < n && j <= arr[i] + i;
j++) {
if (min > jumps[j])
min = jumps[j];
}
// Handle overflow
if (min != INT_MAX)
jumps[i] = min + 1;
else
jumps[i] = min; // or INT_MAX
}
}
return jumps[0];
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 3, 6, 1, 0, 9 };
int size = sizeof(arr) / sizeof(int);
printf("Minimum number of jumps to reach end is %d ",
minJumps(arr, size));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to find Minimum number of jumps to reach end
class GFG {
// Returns Minimum number of jumps to reach end
static int minJumps(int arr[], int n)
{
// jumps[0] will hold the result
int[] jumps = new int[n];
int min;
// Minimum number of jumps needed to reach last
// element from last elements itself is always 0
jumps[n - 1] = 0;
// Start from the second element, move from right to
// left and construct the jumps[] array where
// jumps[i] represents minimum number of jumps
// needed to reach arr[m-1] from arr[i]
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is 0 then arr[n-1] can't be reached
// from here
if (arr[i] == 0)
jumps[i] = Integer.MAX_VALUE;
// If we can directly reach to the end point
// from here then jumps[i] is 1
else if (arr[i] >= n - i - 1)
jumps[i] = 1;
// Otherwise, to find out the minimum number of
// jumps needed to reach arr[n-1], check all the
// points reachable from here and jumps[] value
// for those points
else {
// initialize min value
min = Integer.MAX_VALUE;
// following loop checks with all reachable
// points and takes the minimum
for (int j = i + 1;
j < n && j <= arr[i] + i; j++) {
if (min > jumps[j])
min = jumps[j];
}
// Handle overflow
if (min != Integer.MAX_VALUE)
jumps[i] = min + 1;
else
jumps[i] = min; // or Integer.MAX_VALUE
}
}
return jumps[0];
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 6, 1, 0, 9 };
int size = arr.length;
System.out.println(
"Minimum number of jumps to reach end is "
+ minJumps(arr, size));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python3 program to find Minimum
# number of jumps to reach end
# Returns Minimum number of
# jumps to reach end
def minJumps(arr, n):
# jumps[0] will hold the result
jumps = [0 for i in range(n)]
# Minimum number of jumps needed
# to reach last element from
# last elements itself is always 0
# jumps[n-1] is also initialized to 0
# Start from the second element,
# move from right to left and
# construct the jumps[] array where
# jumps[i] represents minimum number
# of jumps needed to reach arr[m-1]
# form arr[i]
for i in range(n-2, -1, -1):
# If arr[i] is 0 then arr[n-1]
# can't be reached from here
if (arr[i] == 0):
jumps[i] = float('inf')
# If we can directly reach to
# the end point from here then
# jumps[i] is 1
elif (arr[i] >= n - i - 1):
jumps[i] = 1
# Otherwise, to find out the
# minimum number of jumps
# needed to reach arr[n-1],
# check all the points
# reachable from here and
# jumps[] value for those points
else:
# initialize min value
min = float('inf')
# following loop checks with
# all reachable points and
# takes the minimum
for j in range(i + 1, n):
if (j <= arr[i] + i):
if (min > jumps[j]):
min = jumps[j]
# Handle overflow
if (min != float('inf')):
jumps[i] = min + 1
else:
# or INT_MAX
jumps[i] = min
return jumps[0]
# Driver program to test above function
arr = [1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
n = len(arr)
print('Minimum number of jumps to reach',
'end is', minJumps(arr, n-1))
# This code is contributed by Soumen Ghosh
C#
// C# program to find Minimum
// number of jumps to reach end
using System;
class GFG {
// Returns Minimum number
// of jumps to reach end
public static int minJumps(int[] arr, int n)
{
// jumps[0] will
// hold the result
int[] jumps = new int[n];
int min;
// Minimum number of jumps needed to
// reach last element from last elements
// itself is always 0
jumps[n - 1] = 0;
// Start from the second element, move
// from right to left and construct the
// jumps[] array where jumps[i] represents
// minimum number of jumps needed to reach
// arr[m-1] from arr[i]
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is 0 then arr[n-1]
// can't be reached from here
if (arr[i] == 0) {
jumps[i] = int.MaxValue;
}
// If we can directly reach to the end
// point from here then jumps[i] is 1
else if (arr[i] >= n - i - 1) {
jumps[i] = 1;
}
// Otherwise, to find out the minimum
// number of jumps needed to reach
// arr[n-1], check all the points
// reachable from here and jumps[] value
// for those points
else {
// initialize min value
min = int.MaxValue;
// following loop checks with all
// reachable points and takes the minimum
for (int j = i + 1; j < n && j <= arr[i] + i; j++) {
if (min > jumps[j]) {
min = jumps[j];
}
}
// Handle overflow
if (min != int.MaxValue) {
jumps[i] = min + 1;
}
else {
jumps[i] = min; // or Integer.MAX_VALUE
}
}
}
return jumps[0];
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] { 1, 3, 6, 1, 0, 9 };
int size = arr.Length;
Console.WriteLine("Minimum number of"
+ " jumps to reach end is " + minJumps(arr, size));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to find Minimum
// number of jumps to reach end
// Returns Minimum number of jumps
// to reach end
function minJumps($arr, $n)
{
// jumps[0] will hold the result
$jumps[$n] = array();
$min;
// Minimum number of jumps needed
// to reach last element from last
// elements itself is always 0
$jumps[$n-1] = array(0);
// Start from the second element,
// move from right to left and
// construct the jumps[] array where
// jumps[i] represents minimum number
// of jumps needed to reach
// arr[m-1] from arr[i]
for ($i = $n - 2; $i >= 0; $i--)
{
// If arr[i] is 0 then arr[n-1]
// can't be reached from here
if ($arr[$i] == 0)
$jumps[$i] = PHP_INT_MAX;
// If we can directly reach to
// the end point from here then
// jumps[i] is 1
else if ($arr[$i] >= ($n - $i) - 1)
$jumps[$i] = 1;
// Otherwise, to find out the minimum
// number of jumps needed to reach
// arr[n-1], check all the points
// reachable from here and jumps[]
// value for those points
else
{
// initialize min value
$min = PHP_INT_MAX;
// following loop checks with all
// reachable points and takes
// the minimum
for ($j = $i + 1; $j < $n &&
$j <= $arr[$i] + $i; $j++)
{
if ($min > $jumps[$j])
$min = $jumps[$j];
}
// Handle overflow
if ($min != PHP_INT_MAX)
$jumps[$i] = $min + 1;
else
$jumps[$i] = $min; // or INT_MAX
}
}
return $jumps[0];
}
// Driver Code
$arr = array(1, 3, 6, 1, 0, 9);
$size = sizeof($arr);
echo "Minimum number of jumps to reach",
" end is ", minJumps($arr, $size);
// This code is contributed by ajit.
?>
Javascript
<script>
// javascript program to find Minimum
// number of jumps to reach end
// Returns Minimum number
// of jumps to reach end
function minJumps(arr, n)
{
// jumps[0] will
// hold the result
var jumps = Array.from({length: n}, (_, i) => 0);
var min;
// Minimum number of jumps
// needed to reach last
// element from last elements
// itself is always 0
jumps[n - 1] = 0;
// Start from the second
// element, move from right
// to left and construct the
// jumps array where jumps[i]
// represents minimum number of
// jumps needed to reach arr[m-1]
// from arr[i]
for (i = n - 2; i >= 0; i--) {
// If arr[i] is 0 then arr[n-1]
// can't be reached from here
if (arr[i] == 0)
jumps[i] = Number.MAX_VALUE;
// If we can directly reach to
// the end point from here then
// jumps[i] is 1
else if (arr[i] >= n - i - 1)
jumps[i] = 1;
// Otherwise, to find out
// the minimum number of
// jumps needed to reach
// arr[n-1], check all the
// points reachable from
// here and jumps value
// for those points
else {
// initialize min value
min = Number.MAX_VALUE;
// following loop checks
// with all reachable points
// and takes the minimum
for (j = i + 1; j < n && j <= arr[i] + i; j++) {
if (min > jumps[j])
min = jumps[j];
}
// Handle overflow
if (min != Number.MAX_VALUE)
jumps[i] = min + 1;
else
jumps[i] = min; // or Number.MAX_VALUE
}
}
return jumps[0];
}
// Driver Code
var arr = [ 1, 3, 6, 1, 0, 9 ];
var size = arr.length;
document.write("Minimum number of"
+ " jumps to reach end is " + minJumps(arr, size));
// This code is contributed by Amit Katiyar
</script>
Producción:
Minimum number of jumps to reach end is 3
Análisis de Complejidad:
- Complejidad temporal: O(n^2).
Se necesita un recorrido anidado de la array. - Espacio Auxiliar: O(n).
Para almacenar la array DP se necesita espacio lineal.
Número mínimo de saltos para llegar al final | Conjunto 2 (solución O(n))
Gracias a Ashish por sugerir esta solución.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA