Dados dos números enteros N y K , la tarea es encontrar el número total de formas de representar N como la suma de números enteros positivos en el rango [1, K] , donde cada número entero se puede elegir varias veces.
Ejemplos:
Entrada: N = 8, K = 2
Salida: 5
Explicación: Todas las formas posibles de representar N como suma de enteros positivos menores o iguales a K son:
- {1, 1, 1, 1, 1, 1, 1, 1}, la suma es 8.
- {2, 1, 1, 1, 1, 1, 1}, la suma es 8.
- {2, 2, 1, 1, 1, 1}, la suma es 8.
- 2, 2, 2, 1, 1}, la suma es 8.
- {2, 2, 2, 2}}, la suma es 8.
Por lo tanto, el número total de vías es 5.
Entrada: N = 2, K = 2
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las combinaciones posibles de elegir números enteros en el rango [1, K] y contar aquellas combinaciones cuya suma es N.
Complejidad temporal: O(K N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior tiene subproblemas superpuestos y una subestructura óptima . Por lo tanto, para optimizar, se necesita realizar la Programación Dinámica en base a las siguientes observaciones:
- Teniendo en cuenta que dp[i] almacena el número total de formas de representar i como la suma de los números enteros que se encuentran en el rango [1, K] , entonces la transición de estados se puede definir como:
- Para i en el rango [1, K] y para cada j en el rango [1, N]
- El valor de dp[j] es igual a (dp[j]+ dp[j – i]) , para todo j ≥ i .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos dp[] , con todos los elementos como 0 , para almacenar todos los estados recursivos.
- Inicialice dp[0] como 1 .
- Ahora, itera sobre el rango [1, K] usando una variable i y realiza los siguientes pasos:
- Iterar sobre el rango [1, N] , usando una variable j , y actualizar el valor de dp[j] como dp[j]+ dp[j – i] , si j ≥ i .
- Después de completar los pasos anteriores, imprima el valor de dp[N] como resultado.
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 the total number of // ways to represent N as the sum of // integers over the range [1, K] int NumberOfways(int N, int K) { // Initialize a list vector<int> dp(N + 1, 0); // Update dp[0] to 1 dp[0] = 1; // Iterate over the range [1, K + 1] for (int row = 1; row < K + 1; row++) { // Iterate over the range [1, N + 1] for (int col = 1; col < N + 1; col++) { // If col is greater // than or equal to row if (col >= row) // Update current // dp[col] state dp[col] = dp[col] + dp[col - row]; } } // Return the total number of ways return(dp[N]); } // Driver Code int main() { int N = 8; int K = 2; cout << (NumberOfways(N, K)); } // This code is contributed by mohit kumar 29.
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the total number of // ways to represent N as the sum of // integers over the range [1, K] static int NumberOfways(int N, int K) { // Initialize a list int[] dp = new int[N + 1]; // Update dp[0] to 1 dp[0] = 1; // Iterate over the range [1, K + 1] for(int row = 1; row < K + 1; row++) { // Iterate over the range [1, N + 1] for(int col = 1; col < N + 1; col++) { // If col is greater // than or equal to row if (col >= row) // Update current // dp[col] state dp[col] = dp[col] + dp[col - row]; } } // Return the total number of ways return(dp[N]); } // Driver code public static void main(String[] args) { // Given inputs int N = 8; int K = 2; System.out.println(NumberOfways(N, K)); } } // This code is contributed by offbeat
Python
# Python program for the above approach # Function to find the total number of # ways to represent N as the sum of # integers over the range [1, K] def NumberOfways(N, K): # Initialize a list dp = [0] * (N + 1) # Update dp[0] to 1 dp[0] = 1 # Iterate over the range [1, K + 1] for row in range(1, K + 1): # Iterate over the range [1, N + 1] for col in range(1, N + 1): # If col is greater # than or equal to row if (col >= row): # Update current # dp[col] state dp[col] = dp[col] + dp[col - row] # Return the total number of ways return(dp[N]) # Driver Code N = 8 K = 2 print(NumberOfways(N, K))
C#
// C# program for the above approach using System; class GFG { // Function to find the total number of // ways to represent N as the sum of // integers over the range [1, K] static int NumberOfways(int N, int K) { // Initialize a list int[] dp = new int[(N + 1)]; // Update dp[0] to 1 dp[0] = 1; // Iterate over the range [1, K + 1] for (int row = 1; row < K + 1; row++) { // Iterate over the range [1, N + 1] for (int col = 1; col < N + 1; col++) { // If col is greater // than or equal to row if (col >= row) // Update current // dp[col] state dp[col] = dp[col] + dp[col - row]; } } // Return the total number of ways return (dp[N]); } // Driver Code public static void Main() { int N = 8; int K = 2; Console.WriteLine(NumberOfways(N, K)); } } // This code is contributed by ukasp.
Javascript
<script> // Javascript implementation for the above approach // Function to find the total number of // ways to represent N as the sum of // integers over the range [1, K] function NumberOfways(N, K) { // Initialize a list let dp = Array.from({length: N +1}, (_, i) => 0); // Update dp[0] to 1 dp[0] = 1; // Iterate over the range [1, K + 1] for(let row = 1; row < K + 1; row++) { // Iterate over the range [1, N + 1] for(let col = 1; col < N + 1; col++) { // If col is greater // than or equal to row if (col >= row) // Update current // dp[col] state dp[col] = dp[col] + dp[col - row]; } } // Return the total number of ways return(dp[N]); } // Driver Code // Given inputs let N = 8; let K = 2; document.write(NumberOfways(N, K)); </script>
5
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Pranav_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA