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