Número de formas de llegar al Node inicial después de viajar a través de exactamente K aristas en un gráfico completo

Dado un gráfico completo que tiene N Nodes y N*(N-1)/2 aristas y un entero positivo K , la tarea es encontrar el número de formas si comienza en el Node 1 y termina en el mismo Node si exactamente K aristas hay que atravesar. 

Entrada: N = 4, K = 3
Salida: 6
Explicación: Las formas posibles son- 
                            1→2→3→1
                           1→2→4→1
                          1→3→2→1
                          1→3→4→1
                         1→4 →2→1
                         1→4→3→1

Entrada: N = 5, K = 3
Salida: 12

Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar desde cada borde desde el vértice actual, lo que llevará a la solución a un tiempo exponencial.

Complejidad de tiempo: O(N^N)
Espacio auxiliar: O(N), debido al espacio de pila en la llamada de función recursiva .

Enfoque eficiente: este problema tiene la propiedad de subproblemas superpuestos y la propiedad de subestructura óptima . Entonces este problema se puede resolver usando Programación Dinámica . Al igual que otros problemas típicos de Programación Dinámica (DP), se puede evitar volver a calcular los mismos subproblemas construyendo una array temporal que almacene los resultados de los subproblemas. Siga los pasos a continuación para resolver el problema:

  • Inicialice una array dp[] donde dp[i] almacene la cantidad de formas de llegar al i-ésimo Node e inicialice dp[0] como 1.
  • Iterar en el rango [1, K] usando la variable i y realizar los siguientes pasos:
    • Inicialice una variable numWays como 0 para almacenar el número de formas de llegar a todos los Nodes.
    • Iterar en el rango [0, N-1] usando la variable j, luego agregar dp[j] en numWays.
    • Iterar en el rango [0, N-1] usando la variable j, luego actualizar el valor de dp[j] como máximo de dp[j] y numWays – dp[j] .
  • Después de realizar los pasos anteriores, imprima dp[0] como respuesta.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of ways to
// reach from node 1 to 1 again, after
// moving exactly K edges
void numberOfWays(int n, int k)
{
    // Initialize a dp[] array, where dp[i]
    // stores number of ways to reach at
    // a i node
    int dp[1000];
 
    // Initialize the dp array with 0
    for (int i = 0; i < n; i++) {
        dp[i] = 0;
    }
 
    // Base Case
    dp[0] = 1;
 
    // Iterate for the number of edges moved
    for (int i = 1; i <= k; i++) {
        // Sum will store number of ways to
        // reach all the nodes
        int numWays = 0;
 
        // Iterate for every possible state
        // for the current step
        for (int j = 0; j < n; j++) {
            numWays += dp[j];
        }
 
        // Update the value of the dp array
        // after travelling each edge
        for (int j = 0; j < n; j++) {
            dp[j] = numWays - dp[j];
        }
    }
 
    // Print dp[0] as the answer
    cout << dp[0] << endl;
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 5, K = 3;
 
    // Function Call
    numberOfWays(N, K);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to find number of ways to
// reach from node 1 to 1 again, after
// moving exactly K edges
static void numberOfWays(int n, int k)
{
     
    // Initialize a dp[] array, where dp[i]
    // stores number of ways to reach at
    // a i node
    int[] dp = new int[1000];
 
    // Initialize the dp array with 0
    for(int i = 0; i < n; i++)
    {
        dp[i] = 0;
    }
 
    // Base Case
    dp[0] = 1;
 
    // Iterate for the number of edges moved
    for(int i = 1; i <= k; i++)
    {
         
        // Sum will store number of ways to
        // reach all the nodes
        int numWays = 0;
 
        // Iterate for every possible state
        // for the current step
        for(int j = 0; j < n; j++)
        {
            numWays += dp[j];
        }
 
        // Update the value of the dp array
        // after travelling each edge
        for(int j = 0; j < n; j++)
        {
            dp[j] = numWays - dp[j];
        }
    }
 
    // Print dp[0] as the answer
    System.out.println(dp[0] + "\n");
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given Input
    int N = 5, K = 3;
 
    // Function Call
    numberOfWays(N, K);
}
}
 
// This code is contributed by _saurabh_jaiswal

Python3

# Python 3 program for the above approach
 
# Function to find number of ways to
# reach from node 1 to 1 again, after
# moving exactly K edges
def numberOfWays(n, k):
   
    # Initialize a dp[] array, where dp[i]
    # stores number of ways to reach at
    # a i node
    dp = [0 for i in range(1000)]
 
    # Base Case
    dp[0] = 1
 
    # Iterate for the number of edges moved
    for i in range(1, k + 1, 1):
       
        # Sum will store number of ways to
        # reach all the nodes
        numWays = 0
 
        # Iterate for every possible state
        # for the current step
        for j in range(n):
            numWays += dp[j]
 
        # Update the value of the dp array
        # after travelling each edge
        for j in range(n):
            dp[j] = numWays - dp[j]
 
    # Print dp[0] as the answer
    print(dp[0])
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    N = 5
    K = 3
 
    # Function Call
    numberOfWays(N, K)
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find number of ways to
// reach from node 1 to 1 again, after
// moving exactly K edges
static void numberOfWays(int n, int k)
{
     
    // Initialize a dp[] array, where dp[i]
    // stores number of ways to reach at
    // a i node
    int[] dp = new int[1000];
 
    // Initialize the dp array with 0
    for(int i = 0; i < n; i++)
    {
        dp[i] = 0;
    }
 
    // Base Case
    dp[0] = 1;
 
    // Iterate for the number of edges moved
    for(int i = 1; i <= k; i++)
    {
         
        // Sum will store number of ways to
        // reach all the nodes
        int numWays = 0;
 
        // Iterate for every possible state
        // for the current step
        for(int j = 0; j < n; j++)
        {
            numWays += dp[j];
        }
 
        // Update the value of the dp array
        // after travelling each edge
        for(int j = 0; j < n; j++)
        {
            dp[j] = numWays - dp[j];
        }
    }
 
    // Print dp[0] as the answer
    Console.Write(dp[0]);
}
 
// Driver Code
static public void Main ()
{
     
    // Given Input
    int N = 5, K = 3;
 
    // Function Call
    numberOfWays(N, K);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find number of ways to
// reach from node 1 to 1 again, after
// moving exactly K edges
function numberOfWays(n, k)
{
     
    // Initialize a dp[] array, where dp[i]
    // stores number of ways to reach at
    // a i node
    let dp = Array(1000);
 
    // Initialize the dp array with 0
    for(let i = 0; i < n; i++)
    {
        dp[i] = 0;
    }
 
    // Base Case
    dp[0] = 1;
 
    // Iterate for the number of edges moved
    for(let i = 1; i <= k; i++)
    {
         
        // Sum will store number of ways to
        // reach all the nodes
        let numWays = 0;
 
        // Iterate for every possible state
        // for the current step
        for(let j = 0; j < n; j++)
        {
            numWays += dp[j];
        }
 
        // Update the value of the dp array
        // after travelling each edge
        for(let j = 0; j < n; j++)
        {
            dp[j] = numWays - dp[j];
        }
    }
 
    // Print dp[0] as the answer
    document.write(dp[0]);
}
 
// Driver Code
 
 
// Given Input
let N = 5;
let K = 3;
 
// Function Call
numberOfWays(N, K);
 
</script>
Producción

12

Complejidad temporal: O(N×K)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *