Dados dos enteros positivos N y K , la tarea es contar el número de formas de escribir N como una suma de K enteros no negativos.
Ejemplos:
Entrada: N = 2, K = 3
Salida: 6
Explicación:
Las formas totales en que 2 se puede dividir en K enteros no negativos son:
1. (0, 0, 2)
2. (0, 2, 0)
3 (2, 0, 0)
4. (0, 1, 1)
5. (1, 0, 1)
6. (1, 1, 0)Entrada: N = 3, K = 2
Salida: 4
Explicación:
Las formas totales en que se puede dividir 3 en 2 enteros no negativos son:
1. (0, 3)
2. (3, 0)
3. (1, 2)
4. (2, 1)
Enfoque: Este problema se puede resolver usando Programación Dinámica . A continuación se muestran los pasos:
- Inicialice una array 2D como dp[K+1][N+1] donde las filas corresponden al número del elemento que elegimos y las columnas corresponden a la suma correspondiente.
- Comience a llenar la primera fila y columna tomando la suma como K en la tabla anterior dp[][] .
- Supongamos que llegamos a la i-ésima fila y la j-ésima columna, es decir, i elementos que podemos elegir y necesitamos obtener la suma j. Para calcular el número de formas hasta dp[i][j], elija primero (i – 1) elementos y luego (j – x) donde x es la suma de los primeros (i – 1) elementos.
- Repita los pasos anteriores para llenar la array dp[][].
- El valor dp[n][m] dará el resultado requerido.
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 count the number of ways
// to write N as sum of k non-negative
// integers
int countWays(int n, int m)
{
// Initialise dp[][] array
int dp[m + 1][n + 1];
// Only 1 way to choose the value
// with sum K
for (int i = 0; i <= n; i++) {
dp[1][i] = 1;
}
// Initialise sum
int sum;
for (int i = 2; i <= m; i++) {
for (int j = 0; j <= n; j++) {
sum = 0;
// Count the ways from previous
// states
for (int k = 0; k <= j; k++) {
sum += dp[i - 1][k];
}
// Update the sum
dp[i][j] = sum;
}
}
// Return the final count of ways
return dp[m][n];
}
// Driver Code
int main()
{
int N = 2, K = 3;
// Function call
cout << countWays(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count the number of ways
// to write N as sum of k non-negative
// integers
static int countWays(int n, int m)
{
// Initialise dp[][] array
int [][]dp = new int[m + 1][n + 1];
// Only 1 way to choose the value
// with sum K
for(int i = 0; i <= n; i++)
{
dp[1][i] = 1;
}
// Initialise sum
int sum;
for(int i = 2; i <= m; i++)
{
for(int j = 0; j <= n; j++)
{
sum = 0;
// Count the ways from previous
// states
for(int k = 0; k <= j; k++)
{
sum += dp[i - 1][k];
}
// Update the sum
dp[i][j] = sum;
}
}
// Return the final count of ways
return dp[m][n];
}
// Driver Code
public static void main(String[] args)
{
int N = 2, K = 3;
// Function call
System.out.print(countWays(N, K));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to count the number of ways # to write N as sum of k non-negative # integers def countWays(n, m): # Initialise dp[][] array dp = [[ 0 for i in range(n + 1)] for i in range(m + 1)] # Only 1 way to choose the value # with sum K for i in range(n + 1): dp[1][i] = 1 # Initialise sum sum = 0 for i in range(2, m + 1): for j in range(n + 1): sum = 0 # Count the ways from previous # states for k in range(j + 1): sum += dp[i - 1][k] # Update the sum dp[i][j] = sum # Return the final count of ways return dp[m][n] # Driver Code if __name__ == '__main__': N = 2 K = 3 # Function call print(countWays(N, K)) # This code is contributed by Mohit Kumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of ways
// to write N as sum of k non-negative
// integers
static int countWays(int n, int m)
{
// Initialise [,]dp array
int [,]dp = new int[m + 1, n + 1];
// Only 1 way to choose the value
// with sum K
for(int i = 0; i <= n; i++)
{
dp[1, i] = 1;
}
// Initialise sum
int sum;
for(int i = 2; i <= m; i++)
{
for(int j = 0; j <= n; j++)
{
sum = 0;
// Count the ways from previous
// states
for(int k = 0; k <= j; k++)
{
sum += dp[i - 1, k];
}
// Update the sum
dp[i, j] = sum;
}
}
// Return the readonly count of ways
return dp[m, n];
}
// Driver Code
public static void Main(String[] args)
{
int N = 2, K = 3;
// Function call
Console.Write(countWays(N, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of ways
// to write N as sum of k non-negative
// integers
function countWays(n, m)
{
// Initialise dp[][] array
var dp = Array.from(Array(m+1), ()=>Array(n+1));
// Only 1 way to choose the value
// with sum K
for (var i = 0; i <= n; i++) {
dp[1][i] = 1;
}
// Initialise sum
var sum;
for (var i = 2; i <= m; i++) {
for (var j = 0; j <= n; j++) {
sum = 0;
// Count the ways from previous
// states
for (var k = 0; k <= j; k++) {
sum += dp[i - 1][k];
}
// Update the sum
dp[i][j] = sum;
}
}
// Return the final count of ways
return dp[m][n];
}
// Driver Code
var N = 2, K = 3;
// Function call
document.write( countWays(N, K));
</script>
Producción:
6
Complejidad de Tiempo: O(K*N 2 )
Complejidad de Espacio Auxiliar: O(N*K)
Enfoque optimizado: la idea de calcular la suma y luego almacenar la cuenta aumenta la complejidad del tiempo. Podemos disminuirlo almacenando la suma en la tabla dp[][] anterior .
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 count the number of ways
// to write N as sum of k non-negative
// integers
int countWays(int n, int m)
{
// Initialise dp[][] array
int dp[m + 1][n + 1];
// Fill the dp[][] with sum = m
for (int i = 0; i <= n; i++) {
dp[1][i] = 1;
if (i != 0) {
dp[1][i] += dp[1][i - 1];
}
}
// Iterate the dp[][] to fill the
// dp[][] array
for (int i = 2; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Condition for first column
if (j == 0) {
dp[i][j] = dp[i - 1][j];
}
// Else fill the dp[][] with
// sum till (i, j)
else {
dp[i][j] = dp[i - 1][j];
// If reach the end, then
// return the value
if (i == m && j == n) {
return dp[i][j];
}
// Update at current index
dp[i][j] += dp[i][j - 1];
}
}
}
}
// Driver Code
int main()
{
int N = 2, K = 3;
// Function call
cout << countWays(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count the number of ways
// to write N as sum of k non-negative
// integers
static int countWays(int n, int m)
{
// Initialise dp[][] array
int [][]dp = new int[m + 1][n + 1];
// Fill the dp[][] with sum = m
for (int i = 0; i <= n; i++)
{
dp[1][i] = 1;
if (i != 0)
{
dp[1][i] += dp[1][i - 1];
}
}
// Iterate the dp[][] to fill the
// dp[][] array
for (int i = 2; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// Condition for first column
if (j == 0)
{
dp[i][j] = dp[i - 1][j];
}
// Else fill the dp[][] with
// sum till (i, j)
else
{
dp[i][j] = dp[i - 1][j];
// If reach the end, then
// return the value
if (i == m && j == n)
{
return dp[i][j];
}
// Update at current index
dp[i][j] += dp[i][j - 1];
}
}
}
return Integer.MIN_VALUE;
}
// Driver Code
public static void main(String[] args)
{
int N = 2, K = 3;
// Function call
System.out.print(countWays(N, K));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach # Function to count the number of ways # to write N as sum of k non-negative # integers def countWays(n, m): # Initialise dp[][] array dp = [[0 for i in range(n + 1)] for j in range(m + 1)] # Fill the dp[][] with sum = m for i in range(n + 1): dp[1][i] = 1 if (i != 0): dp[1][i] += dp[1][i - 1] # Iterate the dp[][] to fill the # dp[][] array for i in range(2, m + 1): for j in range(n + 1): # Condition for first column if (j == 0): dp[i][j] = dp[i - 1][j] # Else fill the dp[][] with # sum till (i, j) else: dp[i][j] = dp[i - 1][j] # If reach the end, then # return the value if (i == m and j == n): return dp[i][j] # Update at current index dp[i][j] += dp[i][j - 1] # Driver Code N = 2 K = 3 # Function call print(countWays(N, K)) # This code is contributed by ShubhamCoder
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of ways
// to write N as sum of k non-negative
// integers
static int countWays(int n, int m)
{
// Initialise dp[][] array
int [,]dp = new int[m + 1, n + 1];
// Fill the dp[][] with sum = m
for (int i = 0; i <= n; i++)
{
dp[1, i] = 1;
if (i != 0)
{
dp[1, i] += dp[1, i - 1];
}
}
// Iterate the dp[][] to fill the
// dp[][] array
for (int i = 2; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// Condition for first column
if (j == 0)
{
dp[i, j] = dp[i - 1, j];
}
// Else fill the dp[][] with
// sum till (i, j)
else
{
dp[i, j] = dp[i - 1, j];
// If reach the end, then
// return the value
if (i == m && j == n)
{
return dp[i, j];
}
// Update at current index
dp[i, j] += dp[i, j - 1];
}
}
}
return Int32.MinValue;
}
// Driver Code
public static void Main()
{
int N = 2, K = 3;
// Function call
Console.Write(countWays(N, K));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript program for the above approach
// Function to count the number of ways
// to write N as sum of k non-negative
// integers
function countWays(n,m)
{
// Initialise dp[][] array
let dp = new Array(m + 1);
for(let i=0;i<m+1;i++)
{
dp[i]=new Array(n+1);
for(let j=0;j<n+1;j++)
dp[i][j]=0;
}
// Fill the dp[][] with sum = m
for (let i = 0; i <= n; i++)
{
dp[1][i] = 1;
if (i != 0)
{
dp[1][i] += dp[1][i - 1];
}
}
// Iterate the dp[][] to fill the
// dp[][] array
for (let i = 2; i <= m; i++)
{
for (let j = 0; j <= n; j++)
{
// Condition for first column
if (j == 0)
{
dp[i][j] = dp[i - 1][j];
}
// Else fill the dp[][] with
// sum till (i, j)
else
{
dp[i][j] = dp[i - 1][j];
// If reach the end, then
// return the value
if (i == m && j == n)
{
return dp[i][j];
}
// Update at current index
dp[i][j] += dp[i][j - 1];
}
}
}
return Number.MIN_VALUE;
}
// Driver Code
let N = 2, K = 3;
// Function call
document.write(countWays(N, K));
// This code is contributed by patel2127
</script>
Producción:
6
Complejidad de tiempo: O(K*N)
Complejidad de espacio auxiliar: O(N*K)
Publicación traducida automáticamente
Artículo escrito por jay_umiya_mata y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA