Dada una array arr[] que tiene N enteros del rango [1, N] y un número entero K , la tarea es encontrar el costo mínimo posible para dividir la array en subarreglos no vacíos que se puede lograr en función de las siguientes condiciones:
- Si no hay ningún elemento único presente en el subarreglo, el costo es K.
- De lo contrario, el costo es K + Suma de frecuencias de cada elemento repetido .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 1, 2, 3}, K = 2
Salida: 4
Explicación:
dividir el arreglo en subarreglos {1, 2, 3} y {1, 2, 3} genera el costo mínimo, ya que ninguno de los subarreglos contiene ningún elemento repetitivo.
Todas las demás divisiones costarán más, ya que un subarreglo contendrá al menos un elemento repetido.
Por lo tanto, el costo mínimo posible es 4.Entrada: arr[] = {1, 2, 1, 1, 1}, K = 2
Salida: 6
Enfoque ingenuo: la idea más simple para resolver el problema es generar todos los subarreglos posibles para precalcular y almacenar sus respectivos costos. Luego, calcule el costo de cada división posible que se pueda realizar en la array. Finalmente, imprima el costo mínimo de todas las divisiones.
Siga los pasos a continuación para resolver el problema:
- Calcule previamente el costo de cada subarreglo según las condiciones anteriores.
- Genere todas las divisiones posibles que se pueden realizar en la array.
- Para cada división, calcule el costo total de cada subarreglo divisor.
- Seguir manteniendo el coste total mínimo generado y finalmente, imprimir la suma mínima.
Complejidad temporal: O(N!)
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es utilizar la programación dinámica para optimizar el enfoque anterior. Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[] de longitud N con INT_MAX en todos los índices.
- Inicialice el primer elemento de la array con cero .
- Para cualquier índice i, la array dp[i] representa el costo mínimo para dividir la array en subarreglos de 0 a i .
- Para cada índice i , cuente el costo mínimo para todos los índices de i a N.
- Repita este proceso para todos los elementos de la array.
- Devuelva los últimos elementos de dp[] para obtener el costo mínimo de dividir la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to find the minimum cost
// of splitting the array into subarrays
int findMinCost(vector<int>& a, int k)
{
// Size of the array
int n = (int)a.size();
// Get the maximum element
int max_ele = *max_element(a.begin(),
a.end());
// dp[] will store the minimum cost
// upto index i
ll dp[n + 1];
// Initialize the result array
for (int i = 1; i <= n; ++i)
dp[i] = INT_MAX;
// Initialise the first element
dp[0] = 0;
for (int i = 0; i < n; ++i) {
// Create the frequency array
int freq[max_ele + 1];
// Initialize frequency array
memset(freq, 0, sizeof freq);
for (int j = i; j < n; ++j) {
// Update the frequency
freq[a[j]]++;
int cost = 0;
// Counting the cost of
// the duplicate element
for (int x = 0;
x <= max_ele; ++x) {
cost += (freq[x] == 1)
? 0
: freq[x];
}
// Minimum cost of operation
// from 0 to j
dp[j + 1] = min(dp[i] + cost + k,
dp[j + 1]);
}
}
// Total cost of the array
return dp[n];
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 1, 1, 1 };
// Given cost K
int K = 2;
// Function Call
cout << findMinCost(arr, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the
// minimum cost of splitting
// the array into subarrays
static long findMinCost(int[] a,
int k, int n)
{
// Get the maximum element
int max_ele = Arrays.stream(a).max().getAsInt();
// dp[] will store the minimum cost
// upto index i
long[] dp = new long[n + 1];
// Initialize the result array
for (int i = 1; i <= n; ++i)
dp[i] = Integer.MAX_VALUE;
// Initialise the first element
dp[0] = 0;
for (int i = 0; i < n; ++i)
{
// Create the frequency array
int[] freq = new int[max_ele + 1];
for (int j = i; j < n; ++j)
{
// Update the frequency
freq[a[j]]++;
int cost = 0;
// Counting the cost of
// the duplicate element
for (int x = 0; x <= max_ele; ++x)
{
cost += (freq[x] == 1) ? 0 :
freq[x];
}
// Minimum cost of operation
// from 0 to j
dp[j + 1] = Math.min(dp[i] + cost + k,
dp[j + 1]);
}
}
// Total cost of the array
return dp[n];
}
// Driver Code
public static void main(String[] args)
{
int[] arr = {1, 2, 1, 1, 1};
// Given cost K
int K = 2;
int n = arr.length;
// Function Call
System.out.print(findMinCost(arr,
K, n));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach import sys # Function to find the # minimum cost of splitting # the array into subarrays def findMinCost(a, k, n): # Get the maximum element max_ele = max(a) # dp will store the minimum cost # upto index i dp = [0] * (n + 1) # Initialize the result array for i in range(1, n + 1): dp[i] = sys.maxsize # Initialise the first element dp[0] = 0 for i in range(0, n): # Create the frequency array freq = [0] * (max_ele + 1) for j in range(i, n): # Update the frequency freq[a[j]] += 1 cost = 0 # Counting the cost of # the duplicate element for x in range(0, max_ele + 1): cost += (0 if (freq[x] == 1) else freq[x]) # Minimum cost of operation # from 0 to j dp[j + 1] = min(dp[i] + cost + k, dp[j + 1]) # Total cost of the array return dp[n] # Driver Code if __name__ == '__main__': arr = [ 1, 2, 1, 1, 1 ]; # Given cost K K = 2; n = len(arr); # Function call print(findMinCost(arr, K, n)); # This code is contributed by Amit Katiyar
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG{
// Function to find the
// minimum cost of splitting
// the array into subarrays
static long findMinCost(int[] a,
int k, int n)
{
// Get the maximum element
int max_ele = a.Max();
// []dp will store the minimum cost
// upto index i
long[] dp = new long[n + 1];
// Initialize the result array
for (int i = 1; i <= n; ++i)
dp[i] = int.MaxValue;
// Initialise the first element
dp[0] = 0;
for (int i = 0; i < n; ++i)
{
// Create the frequency array
int[] freq = new int[max_ele + 1];
for (int j = i; j < n; ++j)
{
// Update the frequency
freq[a[j]]++;
int cost = 0;
// Counting the cost of
// the duplicate element
for (int x = 0; x <= max_ele; ++x)
{
cost += (freq[x] == 1) ? 0 :
freq[x];
}
// Minimum cost of operation
// from 0 to j
dp[j + 1] = Math.Min(dp[i] + cost + k,
dp[j + 1]);
}
}
// Total cost of the array
return dp[n];
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = {1, 2, 1, 1, 1};
// Given cost K
int K = 2;
int n = arr.Length;
// Function Call
Console.Write(findMinCost(arr,
K, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum cost
// of splitting the array into subarrays
function findMinCost(a, k)
{
// Size of the array
var n = a.length;
// Get the maximum element
var max_ele = a.reduce((a, b) => Math.max(a, b))
// dp[] will store the minimum cost
// upto index i
var dp = Array(n + 1).fill(1000000000);
// Initialise the first element
dp[0] = 0;
for(var i = 0; i < n; ++i)
{
// Create the frequency array
var freq = Array(max_ele + 1).fill(0);
for(var j = i; j < n; ++j)
{
// Update the frequency
freq[a[j]]++;
var cost = 0;
// Counting the cost of
// the duplicate element
for(var x = 0; x <= max_ele; ++x)
{
cost += (freq[x] == 1) ? 0 : freq[x];
}
// Minimum cost of operation
// from 0 to j
dp[j + 1] = Math.min(dp[i] + cost + k,
dp[j + 1]);
}
}
// Total cost of the array
return dp[n];
}
// Driver Code
var arr = [ 1, 2, 1, 1, 1 ];
// Given cost K
var K = 2;
// Function Call
document.write(findMinCost(arr, K));
// This code is contributed by itsok
</script>
Producción:
6
Complejidad de tiempo: O(N 3 ), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)