DP de rangos

Tutorial

La programación dinámica sobre rangos (range DP) es una técnica general para resolver problemas de la forma “¿cuál es la métrica mínima/máxima que se puede obtener sobre un arreglo $A$?” con las siguientes propiedades:

• Un enfoque voraz parece factible, pero da respuestas incorrectas.
• Dados los resultados para cada subarreglo $A[l : x]$ y $A[y : r]$, podemos calcular el resultado para el subarreglo $A[l : r]$ en tiempo $\mathcal O(r - l)$.
• Los subarreglos disjuntos se pueden “combinar” de forma independiente.
• $N$ (el tamaño de $A$) normalmente no es mayor que $500$.

Esta técnica se apoya en la hipótesis de que podemos “combinar” dos subarreglos $A[l : x]$ y $A[x + 1 : r]$ para obtener un candidato para $A[l : r]$. Así podemos iterar sobre todos los $x$ y hallar la mejor respuesta posible para $A[l : r]$. (¡Hay que procesar los subarreglos en orden creciente de longitud!)

Como hay $\mathcal O(N^2)$ subarreglos y procesar cada uno toma tiempo $\mathcal O(N)$, las soluciones que usan esta técnica suelen correr en tiempo $\mathcal O(N^3)$.

Ejemplo - Space Jazz

Explicación

Aunque puede tentarnos usar un enfoque voraz (por ejemplo, borrar repetidamente letras que coinciden hasta que no se pueda más, y después borrar la primera letra “mala”), este enfoque no funciona en entradas como ababa. Junto con el hecho de que aquí $N \leq 500$, esto sugiere usar programación dinámica sobre rangos.

Consideremos el caso de prueba de arriba: ¿con cuál a (si es que con alguna) deberíamos emparejar la primera letra? Como $N$ es pequeño, podemos probar con cada otra a, pero entonces ¿cómo tratamos los “huecos” que quedan en el string?

La observación clave es que si la emparejamos con la segunda a del string, entonces no podemos emparejar las dos b entre sí. Esto significa que en realidad no hace falta preocuparse por los huecos que deja emparejar letras. Más concretamente, si es óptimo emparejar $S[0]$ con $S[i]$, entonces la cantidad mínima de inserciones para $S$ es la suma de las cantidades mínimas de inserciones para $S[1 : i - 1]$ y $S[i + 1 : |S| - 1]$.

Así podemos usar programación dinámica sobre rangos para hallar, para cada subcadena de $S$, la cantidad mínima de inserciones necesarias para convertirla en space jazz.

(¡No hay que olvidar el caso en el que no emparejamos $S[i]$ con nada y simplemente lo duplicamos!)

Implementación

Complejidad temporal: $\mathcal O(N^3)$

#include <bits/stdc++.h>
using namespace std;
 
int dp[502][502];  // Min additions to get "jazz" from index i to j
                   // Inclusive and 0-indexed
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	string s;
	cin >> s;
	for (int j = 0; j <= s.size(); j++) {
		for (int i = 0; i < s.size() - j; i++) {
			// Base case: We just duplicate s[i]
			dp[i][i + j] = dp[i + 1][i + j] + 1;
			for (int k = i + 1; k <= i + j; k++) {
				if (s[k] == s[i]) {  // We try match s[i] and s[k]
					dp[i][i + j] =
					    min(dp[i][i + j], dp[i + 1][k - 1] + dp[k + 1][i + j]);
				}
			}
		}
	}
	cout << dp[0][s.size() - 1] << '\n';
	return 0;
}

import java.io.*;
import java.util.*;
 
public class Jazz {
	public static final int MAXN = 500;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		char[] inp = io.next().toCharArray();
 
		// DP[i][j] is the min number of additions to get "jazz" from index i to
		// j
		int[][] dp = new int[MAXN][MAXN];
		for (int j = 0; j <= inp.length; j++) {
			for (int i = 0; i < inp.length - j; i++) {
				// Base case: duplicate the ith letter.
				dp[i][i + j] = dp[i + 1][i + j] + 1;
 
				for (int k = i + 1; k <= i + j; k++) {
					if (inp[k] == inp[i]) {  // Try to match letters i and k.
						dp[i][i + j] =
						    Math.min(dp[i][i + j], dp[i + 1][k - 1] + dp[k + 1][i + j]);
					}
				}
			}
		}
		io.println(dp[0][inp.length - 1]);
		io.close();
	}
	// CodeSnip{Kattio}
}

s = input()
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
 
for i in range(n + 1):
	for j in range(n - i):
		dp[j][i + j] = dp[j + 1][i + j] + 1
		for k in range(j + 1, i + j + 1):
			if s[k] == s[j]:
				dp[j][i + j] = min(dp[j][i + j], dp[j + 1][k - 1] + dp[k + 1][i + j])
 
print(dp[0][n - 1])

Problemas