Dada una array arr[] que consta de N elementos, la tarea es encontrar las eliminaciones mínimas de subarreglo palindrómico necesarias para eliminar todos los elementos de la array.
Ejemplos:
Entrada: arr[] = {1, 3, 4, 1, 5}, N = 5
Salida: 3
Explicación:
La eliminación de 4 de la array deja {1, 3, 1, 5}.
Eliminación de {1, 3, 1} hojas {5}.
La eliminación de 5 hace que la array esté vacía.
Entrada: arr[] = {1, 2, 3, 5, 3, 1}, N = 5
Salida: 2
Explicación:
Eliminación de {3, 5, 3} deja {1, 2, 1}.
La eliminación de {1, 2, 1} hace que la array esté vacía.
Enfoque:
podemos usar la programación dinámica de intervalos para resolver este problema. Siga los pasos a continuación para resolver el problema:
- Inicialice dp[][] de modo que cada dp[i][j] represente el número mínimo de eliminaciones requeridas desde la i -ésima posición hasta la j -ésima posición.
- Para el intervalo de i a j , la respuesta puede ser la suma de los dos intervalos de i a k y k + 1 a j , es decir:
dp [i][j]= mínimo (dp [i][j], dp [i][k] + dp [k + 1][j]) donde i ≤ k <j
- Además de esta posibilidad, debemos comprobar si arr[i] = arr[j] , entonces dp[i][j] = dp[i + 1][j – 1] .
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;
int dp[550][550];
int minSubarrayRemoval(vector<int>& arr)
{
int i, j, k, l;
int n = arr.size();
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
dp[i][j] = n;
}
}
for (i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (i = 0; i < n - 1; i++) {
if (arr[i] == arr[i + 1]) {
dp[i][i + 1] = 1;
}
else {
dp[i][i + 1] = 2;
}
}
for (l = 2; l < n; l++) {
for (i = 0; i + l < n; i++) {
j = i + l;
if (arr[i] == arr[j]) {
dp[i][j] = dp[i + 1][j - 1];
}
for (k = i; k < j; k++) {
dp[i][j]
= min(
dp[i][j],
dp[i][k]
+ dp[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
// Driver Program
int main()
{
vector<int> arr
= { 2, 3, 1, 2, 2, 1, 2 };
int ans = minSubarrayRemoval(arr);
cout << ans << endl;
}
Java
// Java program for the above approach
class GFG{
static int dp[][] = new int[550][550];
static int minSubarrayRemoval(int arr[])
{
int i, j, k, l;
int n = arr.length;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
dp[i][j] = n;
}
}
for(i = 0; i < n; i++)
{
dp[i][i] = 1;
}
for(i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
dp[i][i + 1] = 1;
}
else
{
dp[i][i + 1] = 2;
}
}
for(l = 2; l < n; l++)
{
for(i = 0; i + l < n; i++)
{
j = i + l;
if (arr[i] == arr[j])
{
dp[i][j] = dp[i + 1][j - 1];
}
for(k = i; k < j; k++)
{
dp[i][j] = Math.min(dp[i][j],
dp[i][k] +
dp[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
// Driver code
public static void main (String[] args)
{
int arr [] = new int[]{ 2, 3, 1, 2, 2, 1, 2 };
int ans = minSubarrayRemoval(arr);
System.out.println(ans);
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 program for the above approach def minSubarrayRemoval(arr): n = len(arr) dp = [] for i in range(n): l = [0] * n for j in range(n): l[j] = n dp.append(l) for i in range(n): dp[i][i] = 1 for i in range(n - 1): if (arr[i] == arr[i + 1]): dp[i][i + 1] = 1 else: dp[i][i + 1] = 2 for l in range(2, n): for i in range(n - l): j = i + l if (arr[i] == arr[j]): dp[i][j] = dp[i + 1][j - 1] for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]) return dp[0][n - 1] # Driver code arr = [ 2, 3, 1, 2, 2, 1, 2 ] ans = minSubarrayRemoval(arr) print(ans) # This code is contributed by shubhamsingh10
C#
// C# program for the above approach
using System;
class GFG{
static int [,]dp = new int[550, 550];
static int minSubarrayRemoval(int []arr)
{
int i, j, k, l;
int n = arr.Length;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
dp[i, j] = n;
}
}
for(i = 0; i < n; i++)
{
dp[i, i] = 1;
}
for(i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
dp[i, i + 1] = 1;
}
else
{
dp[i, i + 1] = 2;
}
}
for(l = 2; l < n; l++)
{
for(i = 0; i + l < n; i++)
{
j = i + l;
if (arr[i] == arr[j])
{
dp[i, j] = dp[i + 1, j - 1];
}
for(k = i; k < j; k++)
{
dp[i, j] = Math.Min(dp[i, j],
dp[i, k] +
dp[k + 1, j]);
}
}
}
return dp[0, n - 1];
}
// Driver code
public static void Main()
{
int []arr = new int[]{ 2, 3, 1, 2, 2, 1, 2 };
int ans = minSubarrayRemoval(arr);
Console.Write(ans);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript program for the above approach
let dp = new Array(550);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
function minSubarrayRemoval(arr)
{
let i, j, k, l;
let n = arr.length;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
dp[i][j] = n;
}
}
for(i = 0; i < n; i++)
{
dp[i][i] = 1;
}
for(i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
dp[i][i + 1] = 1;
}
else
{
dp[i][i + 1] = 2;
}
}
for(l = 2; l < n; l++)
{
for(i = 0; i + l < n; i++)
{
j = i + l;
if (arr[i] == arr[j])
{
dp[i][j] = dp[i + 1][j - 1];
}
for(k = i; k < j; k++)
{
dp[i][j] = Math.min(dp[i][j],
dp[i][k] +
dp[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
// Driver Code
let arr = [ 2, 3, 1, 2, 2, 1, 2 ];
let ans = minSubarrayRemoval(arr);
document.write(ans);
</script>
Producción
2
Complejidad de tiempo: O(n 3 ), donde n es la longitud de la array.
Espacio Auxiliar: O(n 2 )