Rutas que requieren un número mínimo de saltos para llegar al final de la array

Dada una array arr[], donde cada elemento representa el número máximo de pasos que se pueden realizar desde ese elemento, la tarea es imprimir todas las rutas posibles que requieren la cantidad mínima de saltos para llegar al final de la array dada a partir de el primer elemento de la array.

Nota: Si un elemento es 0, entonces no se permiten movimientos desde ese elemento.

Ejemplos:

Entrada: arr[] = {1, 1, 1, 1, 1}
Salida:
0 ⇾ 1 ⇾ 2 ⇾ 3 ⇾ 4
Explicación:
En cada paso, solo se permite un salto.
Por lo tanto, solo existe un camino posible para llegar al final de la array.

Entrada: arr[] = {3, 3, 0, 2, 1, 2, 4, 2, 0, 0}
Salida:
0 ⇾ 3 ⇾ 5 ⇾ 6 ⇾ 9
0 ⇾ 3 ⇾ 5 ⇾ 7 ⇾ 9

Enfoque: La idea es utilizar Programación Dinámica para resolver este problema. Siga los pasos a continuación para resolver el problema:

• Inicialice una array dp[] de tamaño N , donde dp[i] almacena el número mínimo de saltos necesarios para llegar al final de la array arr[N – 1] desde el índice i
• Calcule el número mínimo de pasos necesarios para que cada índice alcance el final de la array iterando sobre los índices N – 2 a 1 . Para cada índice, pruebe todos los pasos posibles que se pueden tomar desde ese índice, es decir, [1, arr[i]] .
• Mientras prueba todos los pasos posibles iterando sobre [1, arr[i]] , para cada índice, actualice y almacene el valor mínimo de dp[i + j] .
• Inicialice una cola de instancia de clase Pair , que almacena el índice de la posición actual y la ruta que se ha recorrido hasta ahora para llegar a ese índice.
• Continúe actualizando el número mínimo de pasos requeridos y, finalmente, imprima las rutas correspondientes a esos recuentos de pasos requeridos.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Pair Struct
struct Pair
{
     
    // Stores the current index
    int idx;
 
    // Stores the path
    // travelled so far
    string psf;
 
    // Stores the minimum jumps
    // required to reach the
    // last index from current index
    int jmps;
};
 
// Minimum jumps required to reach
// end of the array
void minJumps(int arr[], int dp[], int n)
{
    for(int i = 0; i < n; i++)
        dp[i] = INT_MAX;
 
    dp[n - 1] = 0;
 
    for(int i = n - 2; i >= 0; i--)
    {
         
        // Stores the maximum number
        // of steps that can be taken
        // from the current index
        int steps = arr[i];
        int min = INT_MAX;
 
        for(int j = 1;
                j <= steps && i + j < n;
                j++)
        {
             
            // Checking if index stays
            // within bounds
            if (dp[i + j] != INT_MAX &&
                dp[i + j] < min)
            {
                 
                // Stores the minimum
                // number of jumps
                // required to jump
                // from (i + j)-th index
                min = dp[i + j];
            }
        }
         
        if (min != INT_MAX)
            dp[i] = min + 1;
    }
}
 
// Function to find all possible
// paths to reach end of array
// requiring minimum number of steps
void possiblePath(int arr[], int dp[], int n)
{
    queue<Pair> Queue;
    Pair p1 = { 0, "0", dp[0] };
    Queue.push(p1);
 
    while (Queue.size() > 0)
    {
        Pair tmp = Queue.front();
        Queue.pop();
 
        if (tmp.jmps == 0)
        {
            cout << tmp.psf << "\n";
            continue;
        }
 
        for(int step = 1;
                step <= arr[tmp.idx];
                step++)
        {
            if (tmp.idx + step < n &&
                tmp.jmps - 1 == dp[tmp.idx + step])
            {
                 
                // Storing the neighbours
                // of current index element
                string s1 = tmp.psf + " -> " +
                 to_string((tmp.idx + step));
                  
                Pair p2 = { tmp.idx + step, s1,
                           tmp.jmps - 1 };
                           
                Queue.push(p2);
            }
        }
    }
}
 
// Function to find the minimum steps
// and corresponding paths to reach
// end of an array
void Solution(int arr[], int dp[], int size)
{
     
    // dp[] array stores the minimum jumps
    // from each position to last position
    minJumps(arr, dp, size);
 
    possiblePath(arr, dp, size);
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 3, 0, 2, 1,
                  2, 4, 2, 0, 0 };
 
    int size = sizeof(arr) / sizeof(arr[0]);
    int dp[size];
 
    Solution(arr, dp, size);
}
 
// This code is contributed by akhilsaini

// Java Program to implement the
// above approach
 
import java.util.*;
class GFG {
 
    // Pair Class instance
    public static class Pair {
        // Stores the current index
        int idx;
 
        // Stores the path
        // travelled so far
        String psf;
 
        // Stores the minimum jumps
        // required to reach the
        // last index from current index
        int jmps;
 
        // Constructor
        Pair(int idx, String psf, int jmps)
        {
            this.idx = idx;
            this.psf = psf;
            this.jmps = jmps;
        }
    }
 
    // Minimum jumps required to reach
    // end of the array
    public static int[] minJumps(int[] arr)
    {
        int dp[] = new int[arr.length];
 
        Arrays.fill(dp, Integer.MAX_VALUE);
 
        int n = dp.length;
 
        dp[n - 1] = 0;
 
        for (int i = n - 2; i >= 0; i--) {
            // Stores the maximum number
            // of steps that can be taken
            // from the current index
            int steps = arr[i];
            int min = Integer.MAX_VALUE;
 
            for (int j = 1; j <= steps && i + j < n; j++) {
                // Checking if index stays
                // within bounds
                if (dp[i + j] != Integer.MAX_VALUE
                    && dp[i + j] < min) {
                    // Stores the minimum
                    // number of jumps
                    // required to jump
                    // from (i + j)-th index
                    min = dp[i + j];
                }
            }
 
            if (min != Integer.MAX_VALUE)
                dp[i] = min + 1;
        }
        return dp;
    }
 
    // Function to find all possible
    // paths to reach end of array
    // requiring minimum number of steps
    public static void possiblePath(
        int[] arr, int[] dp)
    {
 
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(0, "" + 0, dp[0]));
 
        while (queue.size() > 0) {
            Pair tmp = queue.remove();
 
            if (tmp.jmps == 0) {
                System.out.println(tmp.psf);
                continue;
            }
 
            for (int step = 1;
                 step <= arr[tmp.idx];
                 step++) {
 
                if (tmp.idx + step < arr.length
                    && tmp.jmps - 1 == dp[tmp.idx + step]) {
                    // Storing the neighbours
                    // of current index element
                    queue.add(new Pair(
                        tmp.idx + step,
                        tmp.psf + " -> " + (tmp.idx + step),
                        tmp.jmps - 1));
                }
            }
        }
    }
 
    // Function to find the minimum steps
    // and corresponding paths to reach
    // end of an array
    public static void Solution(int arr[])
    {
        // Stores the minimum jumps from
        // each position to last position
        int dp[] = minJumps(arr);
 
        possiblePath(arr, dp);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 3, 3, 0, 2, 1,
                      2, 4, 2, 0, 0 };
        int size = arr.length;
        Solution(arr);
    }
}

# Python3 program to implement the
# above approach
from queue import Queue
import sys
 
# Pair Class instance
class Pair(object):
     
    # Stores the current index
    idx = 0
 
    # Stores the path
    # travelled so far
    psf = ""
 
    # Stores the minimum jumps
    # required to reach the
    # last index from current index
    jmps = 0
 
    # Constructor
    def __init__(self, idx, psf, jmps):
         
        self.idx = idx
        self.psf = psf
        self.jmps = jmps
 
# Minimum jumps required to reach
# end of the array
def minJumps(arr):
 
    MAX_VALUE = sys.maxsize
    dp = [MAX_VALUE for i in range(len(arr))]
 
    n = len(dp)
 
    dp[n - 1] = 0
 
    for i in range(n - 2, -1, -1):
         
        # Stores the maximum number
        # of steps that can be taken
        # from the current index
        steps = arr[i]
        minimum = MAX_VALUE
 
        for j in range(1, steps + 1, 1):
            if i + j >= n:
                break
             
            # Checking if index stays
            # within bounds
            if ((dp[i + j] != MAX_VALUE) and
                (dp[i + j] < minimum)):
                     
                # Stores the minimum
                # number of jumps
                # required to jump
                # from (i + j)-th index
                minimum = dp[i + j]
 
        if minimum != MAX_VALUE:
            dp[i] = minimum + 1
             
    return dp
 
# Function to find all possible
# paths to reach end of array
# requiring minimum number of steps
def possiblePath(arr, dp):
 
    queue = Queue(maxsize = 0)
    p1 = Pair(0, "0", dp[0])
    queue.put(p1)
 
    while queue.qsize() > 0:
        tmp = queue.get()
 
        if tmp.jmps == 0:
            print(tmp.psf)
            continue
 
        for step in range(1, arr[tmp.idx] + 1, 1):
            if ((tmp.idx + step < len(arr)) and
               (tmp.jmps - 1 == dp[tmp.idx + step])):
               
                # Storing the neighbours
                # of current index element
                p2 = Pair(tmp.idx + step, tmp.psf +
                           " -> " + str((tmp.idx + step)),
                         tmp.jmps - 1)
                          
                queue.put(p2)
 
# Function to find the minimum steps
# and corresponding paths to reach
# end of an array
def Solution(arr):
     
    # Stores the minimum jumps from
    # each position to last position
    dp = minJumps(arr)
     
    possiblePath(arr, dp)
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 3, 3, 0, 2, 1,
            2, 4, 2, 0, 0 ]
    size = len(arr)
 
    Solution(arr)
 
# This code is contributed by akhilsaini

// C# program to implement the
// above approach
using System;
using System.Collections;
 
// Pair Struct
public struct Pair
{
     
    // Stores the current index
    public int idx;
 
    // Stores the path
    // travelled so far
    public string psf;
 
    // Stores the minimum jumps
    // required to reach the
    // last index from current index
    public int jmps;
 
    // Constructor
    public Pair(int idx, String psf, int jmps)
    {
        this.idx = idx;
        this.psf = psf;
        this.jmps = jmps;
    }
}
 
class GFG{
 
// Minimum jumps required to reach
// end of the array
public static int[] minJumps(int[] arr)
{
    int[] dp = new int[arr.Length];
    int n = dp.Length;
 
    for(int i = 0; i < n; i++)
        dp[i] = int.MaxValue;
 
    dp[n - 1] = 0;
 
    for(int i = n - 2; i >= 0; i--)
    {
         
        // Stores the maximum number
        // of steps that can be taken
        // from the current index
        int steps = arr[i];
        int min = int.MaxValue;
 
        for(int j = 1;
                j <= steps && i + j < n;
                j++)
        {
             
            // Checking if index stays
            // within bounds
            if (dp[i + j] != int.MaxValue &&
                dp[i + j] < min)
            {
                 
                // Stores the minimum
                // number of jumps
                // required to jump
                // from (i + j)-th index
                min = dp[i + j];
            }
        }
 
        if (min != int.MaxValue)
            dp[i] = min + 1;
    }
    return dp;
}
 
// Function to find all possible
// paths to reach end of array
// requiring minimum number of steps
public static void possiblePath(int[] arr,
                                int[] dp)
{
    Queue queue = new Queue();
    queue.Enqueue(new Pair(0, "0", dp[0]));
 
    while (queue.Count > 0)
    {
        Pair tmp = (Pair)queue.Dequeue();
 
        if (tmp.jmps == 0)
        {
            Console.WriteLine(tmp.psf);
            continue;
        }
 
        for(int step = 1;
                step <= arr[tmp.idx];
                step++)
        {
            if (tmp.idx + step < arr.Length &&
               tmp.jmps - 1 == dp[tmp.idx + step])
            {
                 
                // Storing the neighbours
                // of current index element
 
                queue.Enqueue(new Pair(
                    tmp.idx + step,
                    tmp.psf + " -> " +
                   (tmp.idx + step),
                   tmp.jmps - 1));
            }
        }
    }
}
 
// Function to find the minimum steps
// and corresponding paths to reach
// end of an array
public static void Solution(int[] arr)
{
     
    // Stores the minimum jumps from
    // each position to last position
    int[] dp = minJumps(arr);
 
    possiblePath(arr, dp);
}
 
// Driver Code
static public void Main()
{
    int[] arr = { 3, 3, 0, 2, 1,
                  2, 4, 2, 0, 0 };
    int size = arr.Length;
     
    Solution(arr);
}
}
 
// This code is contributed by akhilsaini

0 -> 3 -> 5 -> 6 -> 9
0 -> 3 -> 5 -> 7 -> 9

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(N)