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→1Entrada: 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>
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