Dados dos números enteros N y K , la tarea es contar el número de formas de dividir N en K grupos de números enteros positivos de modo que su suma sea N y el número de elementos en los grupos siga un orden no decreciente (es decir, grupo[i] <= grupo[i+1]).
Ejemplos:
Entrada: N = 8, K = 4
Salida: 5
Explicación:
Hay 5 grupos tales que su suma es 8 y el número de enteros positivos en cada grupo es 4.
[1, 1, 1, 5], [1, 1 , 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]
Entrada: N = 24, K = 5
Salida: 164
Explicación:
Hay hay 164 grupos tales que su suma es 24 y el número de enteros positivos en cada grupo es 5
Diferentes enfoques:
1. Enfoque ingenuo (Tiempo: O(N K ), Espacio: O(N))
2. Memoización (Tiempo: O((N 3 *K), Espacio: O(N 2 *K))
3. Programación dinámica ascendente (Tiempo: O(N*K), Espacio: O(N*K))
Enfoque ingenuo: podemos resolver este problema usando recursividad . En cada paso de la recursividad ponga todos los valores mayores que iguales al valor calculado previamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
#include <bits/stdc++.h>
using namespace std;
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k) {
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
int answer = 0;
// put all possible values
// greater equal to prev
for (int i = prev; i <= left; i++) {
answer += calculate(pos + 1, i,
left - i, k);
}
return answer;
}
// Function to count the number of
// ways to divide the number N
int countWaystoDivide(int n, int k)
{
return calculate(0, 1, n, k);
}
// Driver Code
int main()
{
int N = 8;
int K = 4;
cout << countWaystoDivide(N, K);
return 0;
}
Java
// Java implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
import java.util.*;
class GFG{
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
static int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// If N is divides completely
// into less than k groups
if (left == 0)
return 0;
int answer = 0;
// Put all possible values
// greater equal to prev
for(int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return answer;
}
// Function to count the number of
// ways to divide the number N
static int countWaystoDivide(int n, int k)
{
return calculate(0, 1, n, k);
}
// Driver Code
public static void main(String[] args)
{
int N = 8;
int K = 4;
System.out.print(countWaystoDivide(N, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to count the # number of ways to divide N in # groups such that each group # has K number of elements # Function to count the number # of ways to divide the number N # in groups such that each group # has K number of elements def calculate(pos, prev, left, k): # Base Case if (pos == k): if (left == 0): return 1; else: return 0; # If N is divides completely # into less than k groups if (left == 0): return 0; answer = 0; # Put all possible values # greater equal to prev for i in range(prev, left + 1): answer += calculate(pos + 1, i, left - i, k); return answer; # Function to count the number of # ways to divide the number N def countWaystoDivide(n, k): return calculate(0, 1, n, k); # Driver Code if __name__ == '__main__': N = 8; K = 4; print(countWaystoDivide(N, K)); # This code is contributed by 29AjayKumar
C#
// C# implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
using System;
class GFG{
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
static int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// If N is divides completely
// into less than k groups
if (left == 0)
return 0;
int answer = 0;
// Put all possible values
// greater equal to prev
for(int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return answer;
}
// Function to count the number of
// ways to divide the number N
static int countWaystoDivide(int n, int k)
{
return calculate(0, 1, n, k);
}
// Driver Code
public static void Main(String[] args)
{
int N = 8;
int K = 4;
Console.Write(countWaystoDivide(N, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
function calculate(pos, prev,
left, k)
{
// Base Case
if (pos == k) {
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
let answer = 0;
// put all possible values
// greater equal to prev
for (let i = prev; i <= left; i++) {
answer += calculate(pos + 1, i,
left - i, k);
}
return answer;
}
// Function to count the number of
// ways to divide the number N
function countWaystoDivide(n, k)
{
return calculate(0, 1, n, k);
}
// Driver Code
let N = 8;
let K = 4;
document.write(countWaystoDivide(N, K));
// This code is contributed by Mayank Tyagi
</script>
Producción
5
Complejidad temporal: O(N K )
Espacio auxiliar: O(N).
Enfoque de Memoización: En el enfoque anterior podemos ver que estamos resolviendo los subproblemas repetidamente, es decir, sigue la propiedad de Superposición de Subproblemas . Entonces podemos memorizar lo mismo usando la tabla DP.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
#include <bits/stdc++.h>
using namespace std;
// DP Table
int dp[100][100][100];
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k) {
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
// If the subproblem has been
// solved, use the value
if (dp[pos][prev][left] != -1)
return dp[pos][prev][left];
int answer = 0;
// put all possible values
// greater equal to prev
for (int i = prev; i <= left; i++) {
answer += calculate(pos + 1, i,
left - i, k);
}
return dp[pos][prev][left] = answer;
}
// Function to count the number of
// ways to divide the number N in groups
int countWaystoDivide(int n, int k)
{
// Initialize DP Table as -1
memset(dp, -1, sizeof(dp));
return calculate(0, 1, n, k);
}
// Driver Code
int main()
{
int N = 8;
int K = 4;
cout << countWaystoDivide(N, K);
return 0;
}
Java
// Java implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
import java.util.*;
class GFG{
// DP Table
static int [][][]dp = new int[100][100][100];
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
static int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
// If the subproblem has been
// solved, use the value
if (dp[pos][prev][left] != -1)
return dp[pos][prev][left];
int answer = 0;
// put all possible values
// greater equal to prev
for (int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return dp[pos][prev][left] = answer;
}
// Function to count the number of
// ways to divide the number N in groups
static int countWaystoDivide(int n, int k)
{
// Initialize DP Table as -1
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
for (int l = 0; l < 100; l++)
dp[i][j][l] = -1;
}
}
return calculate(0, 1, n, k);
}
// Driver Code
public static void main(String[] args)
{
int N = 8;
int K = 4;
System.out.print(countWaystoDivide(N, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to count the # number of ways to divide N in # groups such that each group # has K number of elements # DP Table dp = [[[0 for i in range(50)] for j in range(50)] for j in range(50)] # Function to count the number # of ways to divide the number N # in groups such that each group # has K number of elements def calculate(pos, prev, left, k): # Base Case if (pos == k): if (left == 0): return 1; else: return 0; # if N is divides completely # into less than k groups if (left == 0): return 0; # If the subproblem has been # solved, use the value if (dp[pos][prev][left] != -1): return dp[pos][prev][left]; answer = 0; # put all possible values # greater equal to prev for i in range(prev,left+1): answer += calculate(pos + 1, i, left - i, k); dp[pos][prev][left] = answer; return dp[pos][prev][left]; # Function to count the number of # ways to divide the number N in groups def countWaystoDivide(n, k): # Initialize DP Table as -1 for i in range(50): for j in range(50): for l in range(50): dp[i][j][l] = -1; return calculate(0, 1, n, k); # Driver Code if __name__ == '__main__': N = 8; K = 4; print(countWaystoDivide(N, K)); # This code is contributed by Rajput-Ji
C#
// C# implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
using System;
class GFG{
// DP Table
static int [,,]dp = new int[50, 50, 50];
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
static int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
// If the subproblem has been
// solved, use the value
if (dp[pos, prev, left] != -1)
return dp[pos, prev, left];
int answer = 0;
// put all possible values
// greater equal to prev
for (int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return dp[pos, prev, left] = answer;
}
// Function to count the number of
// ways to divide the number N in groups
static int countWaystoDivide(int n, int k)
{
// Initialize DP Table as -1
for (int i = 0; i < 50; i++)
{
for (int j = 0; j < 50; j++)
{
for (int l = 0; l < 50; l++)
dp[i, j, l] = -1;
}
}
return calculate(0, 1, n, k);
}
// Driver Code
public static void Main(String[] args)
{
int N = 8;
int K = 4;
Console.Write(countWaystoDivide(N, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
// DP Table
let dp = new Array(500);
for(let i=0;i<500;i++)
{
dp[i]=new Array(500);
for(let j=0;j<500;j++)
{
dp[i][j]=new Array(500);
for(let k=0;k<500;k++)
dp[i][j][k]=0;
}
}
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
function calculate(pos,prev,left,k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
// If the subproblem has been
// solved, use the value
if (dp[pos][prev][left] != -1)
return dp[pos][prev][left];
let answer = 0;
// put all possible values
// greater equal to prev
for (let i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return dp[pos][prev][left] = answer;
}
// Function to count the number of
// ways to divide the number N in groups
function countWaystoDivide(n,k)
{
// Initialize DP Table as -1
for (let i = 0; i < 500; i++)
{
for (let j = 0; j < 500; j++)
{
for (let l = 0; l < 500; l++)
dp[i][j][l] = -1;
}
}
return calculate(0, 1, n, k);
}
// Driver Code
let N = 8;
let K = 4;
document.write(countWaystoDivide(N, K));
// This code is contributed by unknown2108
</script>
Producción:
5
Complejidad temporal: O(N^3 * K)
Espacio auxiliar: O(N^2 * K).
DP de abajo hacia arriba: se nos pide que encontremos CountWaystoDivide (n, k) Entonces, el enfoque de recurrencia y la explicación de DP es:
ContarVíasparaDividir( n , k ) = ContarVíasparaDividir( nk , k ) + ContarVíasparaDividir( n-1 , k-1 )
Explicación:
Divide CountWaystoDivide( n , k ) en dos partes donde
- Si el primer elemento es 1, el resto forma un total de n-1 dividido en k-1, por lo que CountWaystoDivide (n-1, k-1)
- Si el primer elemento es mayor que 1, entonces podemos restar 1 de cada elemento y obtener una partición válida de nk en k partes, por lo tanto CountWaystoDivide( n-1 , k-1 ).
Explicación matemática de DP :
- Como cada grupo debe tener al menos una persona, asigne a cada grupo una persona, entonces nos quedan nk personas, que podemos dividir en 1,2,3… o k grupos. Así nuestro dp será: dp[n][k] = dp[nk][1] + dp[nk][2] + dp[nk][3] + …. + dp[nk][k].
- A primera vista, lo anterior podría dar vibraciones O(N 3 ), pero con un poco de manipulación podemos optimizarlo:
dp[n][k] = dp[(n-1)-(k-1)][1] + dp[(n-1)-(k-1)][2] + … + dp[(n-1)-(k-1)][k-1] + dp[(n-1)-( k-1)][k]
De la recurrencia, podemos escribir:
dp[n][k] = dp[n-1][k-1] + dp[nk][k]
Pasos para resolver el problema usando DP:
- Inicialice una array 2-D dp[][] de tamaño n+1, k+1 donde dp[i][j] almacenará la solución óptima para dividir n en k grupos.
- Para cada valor de i=0 an, dp[n][1] será 1 ya que el total de formas de dividir n en 1 es 1. también dp[0][0] será 1.
Los estados de DP se actualizan de la siguiente manera:
- Si i>=j entonces dp[i][j] = dp[i-1][j-1] + dp[ij][j]
- de lo contrario, ij<0 y dp[ij][j] se vuelven cero, por lo que dp[i][j] = dp[i-1][j-1]
C++
// C++ implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// ways to divide the number N in groups
int countWaystoDivide(int n, int k)
{
if (n < k)
return 0; // When n is less than k, No way to divide
// into groups
vector<vector<int> > dp(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++)
dp[i][1]
= 1; // exact one way to divide n to 1 group
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= k; j++) {
if (i >= j)
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
else
dp[i][j]
= dp[i - 1][j - 1]; // i<j so dp[i-j][j]
// becomes zero
}
}
return dp[n][k]; // returning number of ways to divide N
// in k groups
}
// Driver Code
int main()
{
int N = 8;
int K = 4;
cout << countWaystoDivide(N, K);
return 0;
}
Java
// Java implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
import java.io.*;
class GFG {
static int countWaystoDivide(int n, int k)
{
if (n < k)
return 0; // When n is less than k, No way to divide
// into groups
int [][]dp = new int[n+1][k+1];
for (int i = 1; i <= n; i++)
dp[i][1]
= 1; // exact one way to divide n to 1 group
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= k; j++) {
if (i >= j)
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
else
dp[i][j]
= dp[i - 1][j - 1]; // i<j so dp[i-j][j]
// becomes zero
}
}
return dp[n][k]; // returning number of ways to divide N
// in k groups
}
// Driver code
public static void main (String[] args)
{
int N = 8;
int K = 4;
System.out.println(countWaystoDivide(N, K));
}
}
// This code is contributed by rohitsingh07052.
Python3
# Python3 implementation to count the # number of ways to divide N in # groups such that each group # has K number of elements # DP Table # Function to count the number of # ways to divide the number N in groups def countWaystoDivide(n, k): if(n < k): return 0 dp = [[0 for i in range(k+1)] for i in range(n+1)] for i in range(1, n+1): dp[i][1] = 1 dp[0][0] = 1 for i in range(1, n+1): for j in range(2, k+1): if(i >= j): dp[i][j] = dp[i-1][j-1] + dp[i-j][j] else: dp[i][j] = dp[i-1][j-1] return dp[n][k] # Driver Code if __name__ == '__main__': N = 8 K = 4 print(countWaystoDivide(N, K)) # This code is contributed by Rajput-Ji
C#
// C# implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
using System;
using System.Collections.Generic;
class GFG {
static int countWaystoDivide(int n, int k)
{
if (n < k)
return 0; // When n is less than k, No way to divide
// into groups
int[,] dp = new int[n + 1, k + 1];
for (int i = 1; i <= n; i++)
dp[i, 1] = 1; // exact one way to divide n to 1 group
dp[0, 0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= k; j++) {
if (i >= j)
dp[i,j] = dp[i - j,j] + dp[i - 1,j - 1];
else
dp[i,j] = dp[i - 1, j - 1]; // i<j so dp[i-j][j]
// becomes zero
}
}
return dp[n,k]; // returning number of ways to divide N
// in k groups
}
static void Main() {
int N = 8;
int K = 4;
Console.Write(countWaystoDivide(N, K));
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript implementation to count the
// number of ways to divide N in
// groups such that each group
// has K number of elements
// Function to count the number of
// ways to divide the number N in groups
function countWaystoDivide(n, k)
{
if (n < k)
return 0; // When n is less than k, No way to divide
// into groups
let dp = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
dp[i] = new Array(k + 1);
for(let j = 0; j < k + 1; j++)
{
dp[i][j] = 0;
}
}
for (let i = 1; i <= n; i++)
dp[i][1]
= 1; // exact one way to divide n to 1 group
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 2; j <= k; j++) {
if (i >= j)
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
else
dp[i][j]
= dp[i - 1][j - 1]; // i<j so dp[i-j][j]
// becomes zero
}
}
return dp[n][k]; // returning number of ways to divide N
// in k groups
}
let N = 8;
let K = 4;
document.write(countWaystoDivide(N, K));
// This code is contributed by mukesh07.
</script>
Producción
5
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N * K)