Dado un número entero N, la tarea es encontrar una suma agregada de todas las particiones enteras de este número tal que cada partición no contenga ningún número entero menor que K.
Ejemplos:
Entrada: N = 6 y K = 2
Salida: 24
En este caso, hay 4 particiones válidas.
1) {6}
2) {4, 2}
3) {3, 3}
4) {2, 2, 2}
Por lo tanto, la suma total sería
6 + 4 + 2 + 3 + 3 + 2 + 2 + 2 = 24
Entrada: N = 10 y K = 3
Salida: 50
Aquí, las 5 particiones válidas son:
1) {10}
2) {7, 3}
3) {6, 4}
4) {5, 5}
5) {3 , 3, 4}
La suma total en este caso sería
10 + 7 + 3 + 6 + 4 + 5 + 5 + 3 + 3 + 4 = 50
Enfoque: Este problema tiene una solución recursiva simple . Primero, necesitamos contar el número total de particiones válidas del número N de manera que cada partición contenga números enteros mayores o iguales a K. Entonces, aplicaremos iterativamente nuestra solución recursiva para encontrar particiones válidas que tengan el número entero mínimo K, K+1 , K+2, …, N.
Nuestra respuesta final sería N * no de particiones válidas porque cada partición válida tiene una suma igual a N.
A continuación se presentan algunas ideas clave para diseñar una función recursiva para encontrar el número total de particiones válidas.
- Si N < K entonces no es posible ninguna partición.
- Si N < 2*K entonces solo es posible una partición y esa es el propio número N.
- Podemos encontrar particiones de números de forma recursiva que contengan números enteros al menos iguales a ‘i’ (‘i’ puede ser de K a N) y sumarlos todos para obtener la respuesta final.
Pseudocódigo para la función recursiva para encontrar el número de particiones válidas:
f(N,K):
if N < K
return 0
if N < 2K
return 1
Initialize answer = 1
FOR i from K to N
answer = answer + f(N-i,i)
return answer
A continuación se muestra la solución de programación dinámica:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns total number of valid
// partitions of integer N
long long int countPartitions(int n, int k)
{
// Global declaration of 2D dp array
// which will be later used for memoization
long long int dp[201][201];
// initializing 2D dp array with -1
// we will use this 2D array for memoization
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
dp[i][j] = -1;
}
}
// if this subproblem is already previously
// calculated, then directly return that answer
if (dp[n][k] >= 0)
return dp[n][k];
// if N < K, then no valid
// partition is possible
if (n < k)
return 0;
// if N is between K to 2*K then
// there is only one
// partition and that is the number N itself
if (n < 2 * k)
return 1;
// Initialize answer with 1 as
// the number N itself
// is always a valid partition
long long int answer = 1;
// for loop to iterate over K to N
// and find number of
// possible valid partitions recursively.
for (int i = k; i < n; i++)
answer = answer + countPartitions(n - i, i);
// memoization is done by storing
// this calculated answer
dp[n][k] = answer;
// returning number of valid partitions
return answer;
}
// Driver code
int main()
{
int n = 10, k = 3;
// Printing total number of valid partitions
cout << "Total Aggregate sum of all Valid Partitions: "
<< countPartitions(n, k) * n;
return 0;
}
Java
// Java implementation of
// above approach
class GFG
{
// Function that returns
// total number of valid
// partitions of integer N
static long countPartitions(int n, int k)
{
// Global declaration of 2D
// dp array which will be
// later used for memoization
long[][] dp = new long[201][201];
// initializing 2D dp array
// with -1 we will use this
// 2D array for memoization
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < n + 1; j++)
{
dp[i][j] = -1;
}
}
// if this subproblem is already
// previously calculated, then
// directly return that answer
if (dp[n][k] >= 0)
return dp[n][k];
// if N < K, then no valid
// partition is possible
if (n < k)
return 0;
// if N is between K to 2*K
// then there is only one
// partition and that is
// the number N itself
if (n < 2 * k)
return 1;
// Initialize answer with 1
// as the number N itself
// is always a valid partition
long answer = 1;
// for loop to iterate over
// K to N and find number of
// possible valid partitions
// recursively.
for (int i = k; i < n; i++)
answer = answer +
countPartitions(n - i, i);
// memoization is done by storing
// this calculated answer
dp[n][k] = answer;
// returning number of
// valid partitions
return answer;
}
// Driver code
public static void main(String[] args)
{
int n = 10, k = 3;
// Printing total number
// of valid partitions
System.out.println("Total Aggregate sum of " +
"all Valid Partitions: " +
countPartitions(n, k) * n);
}
}
// This code is contributed by mits
Python3
# Python3 implementation of above approach
# Function that returns total number of valid
# partitions of integer N
def countPartitions(n, k):
# Global declaration of 2D dp array
# which will be later used for memoization
dp = [[0] * 201] * 201
# Initializing 2D dp array with -1
# we will use this 2D array for memoization
for i in range(n + 1):
for j in range(n + 1):
dp[i][j] = -1
# If this subproblem is already previously
# calculated, then directly return that answer
if (dp[n][k] >= 0):
return dp[n][k]
# If N < K, then no valid
# partition is possible
if (n < k) :
return 0
# If N is between K to 2*K then
# there is only one partition
# and that is the number N itself
if (n < 2 * k):
return 1
# Initialize answer with 1 as
# the number N itself
# is always a valid partition
answer = 1
# For loop to iterate over K to N
# and find number of possible valid
# partitions recursively.
for i in range(k, n):
answer = (answer +
countPartitions(n - i, i))
# Memoization is done by storing
# this calculated answer
dp[n][k] = answer
# Returning number of valid partitions
return answer
# Driver code
n = 10
k = 3
# Printing total number of valid partitions
print("Total Aggregate sum of all "
"Valid Partitions: ",
countPartitions(n, k) * n)
# This code is contributed by sanjoy_62
C#
// C# implementation of above approach
using System;
class GFG
{
// Function that returns total number of valid
// partitions of integer N
public static long countPartitions(int n, int k)
{
// Global declaration of 2D dp array
// which will be later used for memoization
long[,] dp = new long[201,201];
// initializing 2D dp array with -1
// we will use this 2D array for memoization
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
dp[i,j] = -1;
}
}
// if this subproblem is already previously
// calculated, then directly return that answer
if (dp[n,k] >= 0)
return dp[n,k];
// if N < K, then no valid
// partition is possible
if (n < k)
return 0;
// if N is between K to 2*K then
// there is only one
// partition and that is the number N itself
if (n < 2 * k)
return 1;
// Initialize answer with 1 as
// the number N itself
// is always a valid partition
long answer = 1;
// for loop to iterate over K to N
// and find number of
// possible valid partitions recursively.
for (int i = k; i < n; i++)
answer = answer + countPartitions(n - i, i);
// memoization is done by storing
// this calculated answer
dp[n,k] = answer;
// returning number of valid partitions
return answer;
}
// Driver code
static void Main()
{
int n = 10, k = 3;
// Printing total number of valid partitions
Console.Write("Total Aggregate sum of all Valid Partitions: " + countPartitions(n, k) * n);
}
//This code is contributed by DrRoot_
}
Javascript
<script>
// Javascript implementation of above approach
// Function that returns
// total number of valid
// partitions of integer N
function countPartitions(n, k)
{
// Global declaration of 2D
// dp array which will be
// later used for memoization
let dp = new Array(201);
// initializing 2D dp array
// with -1 we will use this
// 2D array for memoization
for (let i = 0; i < n + 1; i++)
{
dp[i] = new Array(201);
for (let j = 0; j < n + 1; j++)
{
dp[i][j] = -1;
}
}
// if this subproblem is already
// previously calculated, then
// directly return that answer
if (dp[n][k] >= 0)
return dp[n][k];
// if N < K, then no valid
// partition is possible
if (n < k)
return 0;
// if N is between K to 2*K
// then there is only one
// partition and that is
// the number N itself
if (n < 2 * k)
return 1;
// Initialize answer with 1
// as the number N itself
// is always a valid partition
let answer = 1;
// for loop to iterate over
// K to N and find number of
// possible valid partitions
// recursively.
for (let i = k; i < n; i++)
answer = answer + countPartitions(n - i, i);
// memoization is done by storing
// this calculated answer
dp[n][k] = answer;
// returning number of
// valid partitions
return answer;
}
let n = 10, k = 3;
// Printing total number
// of valid partitions
document.write("Total Aggregate sum of " +
"all Valid Partitions: " +
countPartitions(n, k) * n);
// This code is contributed by rameshtravel07.
</script>
Producción:
Total Aggregate sum of all Valid Partitions: 50
Complejidad temporal: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por meet97_patel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA