Maneras de sumar a N usando Números Naturales hasta K con repeticiones permitidas

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, 1}, la suma es 8.
  2. {2, 1, 1, 1, 1, 1, 1}, la suma es 8.
  3. {2, 2, 1, 1, 1, 1}, la suma es 8.
  4. 2, 2, 2, 1, 1}, la suma es 8.
  5. {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>
Producción: 

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

Deja una respuesta

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