Dada una array de números donde cada elemento representa el número máximo de saltos que se pueden realizar desde ese elemento. Para cada elemento de la array, cuente la cantidad de formas en que se pueden realizar saltos desde ese elemento para llegar al final de la array. Si un elemento es 0 , entonces no se puede realizar un movimiento a través de ese elemento. El elemento que no puede llegar al final debe tener una cuenta » -1 «.
Ejemplos:
Entrada: {3, 2, 0, 1}
Salida: 2 1 -1 0
Explicación:
- Para 3 el número de pasos o saltos que se pueden dar es 1, 2 o 3. Las diferentes formas son:
3 -> 2 -> 1
3 -> 1- Para 2, el número de pasos o saltos que se pueden dar es 1 o 2. Las diferentes formas son:
2 -> 1- Para 0 el número de pasos o saltos que se pueden dar es 0. No se puede avanzar desde este punto.
- Para 1, la cantidad de pasos o saltos que se pueden dar es 1. Pero el elemento está al final, por lo que no se requiere ningún salto.
Entrada: {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9}
Salida: 52 52 28 16 8 -1 -1 4 2 1 0
Este problema es una variación del Número mínimo de saltos para llegar al final (Método 3) . Aquí necesitamos contar todas las formas de llegar al final desde cada celda.
La solución es una versión modificada de la solución al problema del Número mínimo de saltos para llegar al final (Método 3) .
Este problema tiene como objetivo contar las diferentes formas de saltar de cada elemento para llegar al final. Para cada elemento, el recuento se calcula sumando los recuentos de todos los elementos anteriores que pueden llegar al final y a los que el elemento actual podría llegar a + 1 (si el elemento puede llegar directamente al final).
Algoritmo:
countWays(arr, n)
Initialize array count_jump[n] = {0}
count_jump[n-1] = 0
for i = n-2 to 0
if arr[i] >= (n-i-1)
count_jump[i]++
for j=i+1; j < n-1 && j <= arr[i]+i; i++
if count_jump[j] != -1
count_jump[i] += count_jump[j]
if count_jump[i] == 0
count_jump[i] = -1
for i = 0 to n-1
print count_jump[i]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count number
// of ways to jump to reach end
#include <bits/stdc++.h>
using namespace std;
// function to count ways to jump to
// reach end for each array element
void countWaysToJump(int arr[], int n)
{
// count_jump[i] store number of ways
// arr[i] can reach to the end
int count_jump[n];
memset(count_jump, 0, sizeof(count_jump));
// Last element does not require to jump.
// Count ways to jump for remaining
// elements
for (int i=n-2; i>=0; i--)
{
// if the element can directly
// jump to the end
if (arr[i] >= n - i - 1)
count_jump[i]++;
// add the count of all the elements
// that can reach to end and arr[i] can
// reach to them
for (int j=i+1; j < n-1 && j <= arr[i] + i; j++)
// if element can reach to end then add
// its count to count_jump[i]
if (count_jump[j] != -1)
count_jump[i] += count_jump[j];
// if arr[i] cannot reach to the end
if (count_jump[i] == 0)
count_jump[i] = -1;
}
// print count_jump for each
// array element
for (int i=0; i<n; i++)
cout << count_jump[i] << " ";
}
// Driver program to test above
int main()
{
int arr[] = {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
countWaysToJump(arr, n);
return 0;
}
Java
// Java implementation to count number
// of ways to jump to reach end
import java.util.Arrays;
class GFG {
// function to count ways to jump to
// reach end for each array element
static void countWaysToJump(int arr[], int n)
{
// count_jump[i] store number of ways
// arr[i] can reach to the end
int count_jump[] = new int[n];
Arrays.fill(count_jump, 0);
// Last element does not require to jump.
// Count ways to jump for remaining
// elements
for (int i = n-2; i >= 0; i--)
{
// if the element can directly
// jump to the end
if (arr[i] >= n - i - 1)
count_jump[i]++;
// add the count of all the elements
// that can reach to end and arr[i] can
// reach to them
for (int j = i+1; j < n-1 && j <= arr[i] + i; j++)
// if element can reach to end then add
// its count to count_jump[i]
if (count_jump[j] != -1)
count_jump[i] += count_jump[j];
// if arr[i] cannot reach to the end
if (count_jump[i] == 0)
count_jump[i] = -1;
}
// print count_jump for each
// array element
for (int i = 0; i < n; i++)
System.out.print(count_jump[i] + " ");
}
//driver code
public static void main (String[] args)
{
int arr[] = {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9};
int n = arr.length;
countWaysToJump(arr, n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 implementation to count # number of ways to jump to reach end # Function to count ways to jump to # reach end for each array element def countWaysToJump(arr, n): # count_jump[i] store number of ways # arr[i] can reach to the end count_jump = [0 for i in range(n)] # Last element does not require # to jump. Count ways to jump for # remaining elements for i in range(n - 2, -1, -1): # if the element can directly # jump to the end if (arr[i] >= n - i - 1): count_jump[i] += 1 # Add the count of all the elements # that can reach to end and arr[i] # can reach to them j = i + 1 while(j < n-1 and j <= arr[i] + i): # if element can reach to end then # add its count to count_jump[i] if (count_jump[j] != -1): count_jump[i] += count_jump[j] j += 1 # if arr[i] cannot reach to the end if (count_jump[i] == 0): count_jump[i] = -1 # print count_jump for each # array element for i in range(n): print(count_jump[i], end = " ") # Driver code arr = [1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9] n = len(arr) countWaysToJump(arr, n) # This code is contributed by Anant Agarwal.
C#
// C# implementation to count number
// of ways to jump to reach end
using System;
class GFG {
// function to count ways to jump to
// reach end for each array element
static void countWaysToJump(int[] arr, int n)
{
// count_jump[i] store number of ways
// arr[i] can reach to the end
int[] count_jump = new int[n];
for(int i = 0; i < n; i++)
count_jump[i] = 0;
// Last element does not require to jump.
// Count ways to jump for remaining
// elements
for (int i = n-2; i >= 0; i--)
{
// if the element can directly
// jump to the end
if (arr[i] >= n - i - 1)
count_jump[i]++;
// add the count of all the elements
// that can reach to end and arr[i] can
// reach to them
for (int j = i+1; j < n-1 && j <= arr[i] + i; j++)
// if element can reach to end then add
// its count to count_jump[i]
if (count_jump[j] != -1)
count_jump[i] += count_jump[j];
// if arr[i] cannot reach to the end
if (count_jump[i] == 0)
count_jump[i] = -1;
}
// print count_jump for each
// array element
for (int i = 0; i < n; i++)
Console.Write(count_jump[i] + " ");
}
// Driver code
public static void Main ()
{
int[] arr = {1, 3, 5, 8, 9,
1, 0, 7, 6, 8, 9};
int n = arr.Length;
countWaysToJump(arr, n);
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP implementation to count number
// of ways to jump to reach end
// function to count ways to jump to
// reach end for each array element
function countWaysToJump($arr, $n)
{
// count_jump[i] store number of ways
// arr[i] can reach to the end
$count_jump;
for($i = 0; $i < $n; $i++)
$count_jump[$i] = 0;
// Last element does not require to jump.
// Count ways to jump for remaining
// elements
for ($i = $n - 2; $i >= 0; $i--)
{
// if the element can directly
// jump to the end
if ($arr[$i] >= $n - $i - 1)
$count_jump[$i]++;
// add the count of all the elements
// that can reach to end and arr[i]
// can reach to them
for ($j = $i + 1; $j < $n - 1 &&
$j <= $arr[$i] + $i; $j++)
// if element can reach to end then
// add its count to count_jump[i]
if ($count_jump[$j] != -1)
$count_jump[$i] += $count_jump[$j];
// if arr[i] cannot reach to the end
if ($count_jump[$i] == 0)
$count_jump[$i] = -1;
}
// print count_jump for each
// array element
for ($i = 0; $i < $n; $i++)
echo $count_jump[$i] . " ";
}
// Driver Code
$arr = array(1, 3, 5, 8, 9, 1,
0, 7, 6, 8, 9);
$n = count($arr);
countWaysToJump($arr, $n);
// This code is contributed by Rajput-Ji
?>
Javascript
<script>
// Javascript implementation to count number
// of ways to jump to reach end
// function to count ways to jump to
// reach end for each array element
function countWaysToJump(arr,n)
{
// count_jump[i] store number of ways
// arr[i] can reach to the end
let count_jump = new Array(n);
for(let i=0;i<n;i++)
{
count_jump[i]=0;
}
// Last element does not require to jump.
// Count ways to jump for remaining
// elements
for (let i = n-2; i >= 0; i--)
{
// if the element can directly
// jump to the end
if (arr[i] >= n - i - 1)
count_jump[i]++;
// add the count of all the elements
// that can reach to end and arr[i] can
// reach to them
for (let j = i+1; j < n-1 && j <= arr[i] + i; j++)
// if element can reach to end then add
// its count to count_jump[i]
if (count_jump[j] != -1)
count_jump[i] += count_jump[j];
// if arr[i] cannot reach to the end
if (count_jump[i] == 0)
count_jump[i] = -1;
}
// print count_jump for each
// array element
for (let i = 0; i < n; i++)
document.write(count_jump[i] + " ");
}
//driver code
let arr=[1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9];
let n = arr.length;
countWaysToJump(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
52 52 28 16 8 -1 -1 4 2 1 0
Complejidad de tiempo: O(n 2 ), donde n es el tamaño de la array dada.
Espacio auxiliar: O (n), ya que estamos creando una array count_jump de tamaño n.
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