Dada una array arr de longitud N , la tarea es minimizar su longitud realizando las siguientes operaciones:
- Elimine cualquier par igual adyacente (es decir, si arr[i] = arr[i+1] ) y reemplácelo con una sola instancia de arr[i] + 1 .
- Cada operación disminuye la longitud de la array en 1.
- Repetir la operación hasta que no se puedan realizar más reducciones.
Ejemplos:
Entrada: arr = {3, 3, 4, 4, 4, 3, 3}
Salida: 2
Explicación:
combine los dos primeros 3 y reemplácelos por 4. Array actualizada: {4, 4, 4, 4, 3, 3 }
Combina los dos primeros 4 y reemplázalos por 5. Array actualizada: {5, 4, 4, 3, 3}
Combina los dos 4 y reemplázalos por 5. Array actualizada: {5, 5, 3, 3}
Combina los dos 5 y reemplácelos por 6. Array actualizada: {6, 3, 3}
Combine los dos 3 y reemplácelos por 4. Array actualizada: {6, 4}
Por lo tanto, la longitud mínima de la array reducida = 2
Entrada: arr = {4, 3, 2, 2, 3}
Resultado: 2
Explicación:
combine los dos 2 y reemplácelos por 3. Array actualizada: {4, 3, 3, 3}
Combina los dos primeros 3 y reemplázalos por 4. Array actualizada: {4, 4, 3}
Combina los dos 4 y reemplázalos por 5. Array actualizada: {5, 3}
Por lo tanto, la longitud mínima de la array reducida = 2
Enfoque: El problema mencionado anteriormente se puede resolver usando Programación Dinámica . Se puede observar que cada elemento del arreglo final será el resultado del reemplazo de un número de elementos en el segmento correspondiente. Entonces, nuestro objetivo es encontrar la partición mínima de la array en segmentos, donde cada segmento se puede convertir en un solo elemento mediante una serie de operaciones.
Definamos el siguiente estado de la tabla de programación dinámica :
dp[i][j] = valor del único elemento restante
cuando el subarreglo del índice i al j se reduce mediante una serie de operaciones o es igual a -1 cuando el subarreglo no se puede reducir a un solo elemento.
Para calcular dp[i][j]:
- Si i = j, dp[i][j] = a[i]
- Iterar desde [i, j-1], dejar que el índice de recorrido sea k (i <= k < j). Para cualquier k si dp[i][k] = dp[k+1][j] , esto significa que el subarreglo [i, j] se puede dividir en dos partes y ambas partes tienen el mismo valor final, por lo que estas dos partes se pueden combinar, es decir , dp[i][j] = dp[i][k] + 1 .
Para calcular las particiones mínimas , crearemos otra tabla dp en la que se almacena el resultado final. Esta tabla tiene el siguiente estado:
dp1[i] = partición mínima del subarreglo [1: i]
que es el tamaño mínimo del arreglo hasta i después de realizar las operaciones anteriores.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation to find the
// minimum length of the array
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// length of minimized array
int minimalLength(int a[], int n)
{
// Creating the required dp tables
int dp[n + 1][n + 1], dp1[n];
int i, j, k;
// Initialising the dp table by -1
memset(dp, -1, sizeof(dp));
for (int size = 1; size <= n; size++) {
for (i = 0; i < n - size + 1; i++) {
j = i + size - 1;
// base case
if (i == j)
dp[i][j] = a[i];
else {
for (k = i; k < j; k++) {
// Check if the two subarray
// can be combined
if (dp[i][k] != -1
&& dp[i][k] == dp[k + 1][j])
dp[i][j] = dp[i][k] + 1;
}
}
}
}
// Initialising dp1 table with max value
for (i = 0; i < n; i++)
dp1[i] = 1e7;
for (i = 0; i < n; i++) {
for (j = 0; j <= i; j++) {
// Check if the subarray can be
// reduced to a single element
if (dp[j][i] != -1) {
if (j == 0)
dp1[i] = 1;
// Minimal partition
// of [1: j-1] + 1
else
dp1[i] = min(
dp1[i],
dp1[j - 1] + 1);
}
}
}
return dp1[n - 1];
}
// Driver code
int main()
{
int n = 7;
int a[n] = { 3, 3, 4, 4, 4, 3, 3 };
cout << minimalLength(a, n);
return 0;
}
Java
// Java implementation to find the
// minimum length of the array
import java.util.*;
class GFG{
// Function to find the
// length of minimized array
static int minimalLength(int a[], int n)
{
// Creating the required dp tables
int [][]dp = new int[n + 1][n + 1];
int []dp1 = new int[n];
int i, j, k;
// Initialising the dp table by -1
for (i = 0; i < n + 1; i++) {
for (j = 0; j < n + 1; j++) {
dp[i][j] = -1;
}
}
for (int size = 1; size <= n; size++) {
for (i = 0; i < n - size + 1; i++) {
j = i + size - 1;
// base case
if (i == j)
dp[i][j] = a[i];
else {
for (k = i; k < j; k++) {
// Check if the two subarray
// can be combined
if (dp[i][k] != -1
&& dp[i][k] == dp[k + 1][j])
dp[i][j] = dp[i][k] + 1;
}
}
}
}
// Initialising dp1 table with max value
for (i = 0; i < n; i++)
dp1[i] = (int) 1e7;
for (i = 0; i < n; i++) {
for (j = 0; j <= i; j++) {
// Check if the subarray can be
// reduced to a single element
if (dp[j][i] != -1) {
if (j == 0)
dp1[i] = 1;
// Minimal partition
// of [1: j-1] + 1
else
dp1[i] = Math.min(
dp1[i],
dp1[j - 1] + 1);
}
}
}
return dp1[n - 1];
}
// Driver code
public static void main(String[] args)
{
int n = 7;
int a[] = { 3, 3, 4, 4, 4, 3, 3 };
System.out.print(minimalLength(a, n));
}
}
// This code contributed by Princi Singh
Python3
# Python3 implementation to find the # minimum length of the array import numpy as np # Function to find the # length of minimized array def minimalLength(a, n) : # Creating the required dp tables # Initialising the dp table by -1 dp = np.ones((n + 1,n + 1)) * -1; dp1 = [0]*n; for size in range(1, n + 1) : for i in range( n - size + 1) : j = i + size - 1; # base case if (i == j) : dp[i][j] = a[i]; else : for k in range(i,j) : # Check if the two subarray # can be combined if (dp[i][k] != -1 and dp[i][k] == dp[k + 1][j]) : dp[i][j] = dp[i][k] + 1; # Initialising dp1 table with max value for i in range(n) : dp1[i] = int(1e7); for i in range(n) : for j in range(i + 1) : # Check if the subarray can be # reduced to a single element if (dp[j][i] != -1) : if (j == 0) : dp1[i] = 1; # Minimal partition # of [1: j-1] + 1 else : dp1[i] = min( dp1[i], dp1[j - 1] + 1); return dp1[n - 1]; # Driver code if __name__ == "__main__" : n = 7; a = [ 3, 3, 4, 4, 4, 3, 3 ]; print(minimalLength(a, n)); # This code is contributed by Yash_R
C#
// C# implementation to find the
// minimum length of the array
using System;
class GFG{
// Function to find the
// length of minimized array
static int minimalLength(int []a, int n)
{
// Creating the required dp tables
int [,]dp = new int[n + 1, n + 1];
int []dp1 = new int[n];
int i, j, k;
// Initialising the dp table by -1
for (i = 0; i < n + 1; i++) {
for (j = 0; j < n + 1; j++) {
dp[i, j] = -1;
}
}
for (int size = 1; size <= n; size++) {
for (i = 0; i < n - size + 1; i++) {
j = i + size - 1;
// base case
if (i == j)
dp[i, j] = a[i];
else {
for (k = i; k < j; k++) {
// Check if the two subarray
// can be combined
if (dp[i, k] != -1
&& dp[i, k] == dp[k + 1, j])
dp[i, j] = dp[i, k] + 1;
}
}
}
}
// Initialising dp1 table with max value
for (i = 0; i < n; i++)
dp1[i] = (int) 1e7;
for (i = 0; i < n; i++) {
for (j = 0; j <= i; j++) {
// Check if the subarray can be
// reduced to a single element
if (dp[j, i] != -1) {
if (j == 0)
dp1[i] = 1;
// Minimal partition
// of [1: j-1] + 1
else
dp1[i] = Math.Min(
dp1[i],
dp1[j - 1] + 1);
}
}
}
return dp1[n - 1];
}
// Driver code
public static void Main(string[] args)
{
int n = 7;
int []a = { 3, 3, 4, 4, 4, 3, 3 };
Console.Write(minimalLength(a, n));
}
}
// This code is contributed by Yash_R
Javascript
<script>
// Javascript implementation to find the
// minimum length of the array
// Function to find the
// length of minimized array
function minimalLength(a, n)
{
// Creating the required dp t0ables
// Initialising the dp table by -1
var i, j, k;
var dp = Array(n+1).fill(Array(n+1).fill(-1));
var dp1 = Array(n).fill(0);
for (var size = 1; size <= n; size++) {
for (i = 0; i < n - size + 1; i++) {
j = i + size - 1;
// base case
if (i == j)
dp[i][j] = a[i];
else {
for (k = i; k < j; k++) {
// Check if the two subarray
// can be combined
if (dp[i][k] != -1
&& dp[i][k] == dp[k + 1][j])
dp[i][j] = dp[i][k] + 1;
}
}
}
}
// Initialising dp1 table with max value
for (i = 0; i < n; i++)
dp1[i] = 1000000000;
for (i = 0; i < n; i++)
{
for (j = 0; j <= i; j++)
{
// Check if the subarray can be
// reduced to a single element
if (dp[j][i] != -1) {
if (j == 0)
dp1[i] = 2;
// Minimal partition
// of [1: j-1] + 1
else
dp1[i] = Math.min(dp1[i], dp1[j - 1] + 1);
}
}
}
return dp1[n - 1];
}
// Driver code
var n = 7;
var a = [ 3, 3, 4, 4, 4, 3, 3 ];
document.write(minimalLength(a, n));
// This code is contributed by rrrtnx.
</script>
2
Complejidad temporal: O(N 3 )