Antes de leer este manual, conviene haber visto:
Este manual trata sobre una colección de "trucos" relacionados con la programación dinámica que permiten mejorar la complejidad de nuestras soluciones.
Agrupar elementos del mismo peso en problemas tipo Subset sum/Knapsack
Unos problemas típicos de programación dinámica son los problemas de tipo Knapsack o Subset sum. Por ejemplo, consideremos el siguiente problema (problema de la partición): dados $n$ enteros positivos $a_1, \ldots, a_n$ con $\sum_{i=1}^n a_i = 2S$, determinar si existe un subconjunto $I \subseteq [n]$ tal que $\sum_{i\in I} a_i = S$.
La solución clásica con programación dinámica usa tiempo $O(nS)$. Hay una forma ingeniosa de mejorar la complejidad si $n$ es relativamente grande comparado con $S$: observemos que, en este caso, la mayoría de los números serán pequeños y, en particular, habrá muchos números pequeños repetidos. La idea es que, si tenemos un número $x$ repetido $3$ veces, podemos sustituir los $3$ elementos con valor $x$ por un elemento con valor $x$ y otro con valor $2x$ sin que cambie la respuesta. Esto es porque si usamos 2 de los 3 elementos con valor $x$ en el subconjunto seleccionado podemos utilizar $2x$ en su lugar, y si usamos los 3 elementos con valor $x$ podemos en su lugar usar uno con valor $x$ y otro con $2x$.
Así, podemos ir reduciendo el valor de $n$ aplicando esta operación de sustituir 3 valores $x,x,x$ por 2 valores $x,2x$. Para aplicar la operación de forma sencilla podemos almacenar el multiconjunto en un mapa (valor, número de elementos con ese valor). Si aplicamos la operación hasta que cada valor esté repetido como mucho $2$ veces, el número total de elementos restantes (el nuevo valor de $n$, por así decirlo) será $O\left(\sqrt{S}\right)$, por tanto podemos solucionar el problema en tiempo $O\left(n \log n + S\sqrt{S}\right)$. (La razón por la que el nuevo valor de $n$ es $O\left(\sqrt{S}\right)$ es porque si $x_1, \ldots, x_n$ son $n$ enteros distintos, $\sum_{i=1}^n x_i \geq \sum_{i=1}^n i = \Omega(n^2)$).
Optimización de Knuth
Esta optimización fue diseñada por primera vez por Donald Knuth para solucionar el problema del árbol binario de búsqueda óptimo en $O(n^2)$. Veamos en qué consiste este problema.
Tienes una serie de $n$ valores $a_1 < a_2 < \ldots < a_n$ y quieres almacenarlos en un árbol binario de búsqueda (es decir: en cada nodo del árbol binario hay un valor, y todos los valores en los descendientes izquierdos de un nodo son menores que el valor del nodo, y todos los valores en los descendientes derechos de un nodo son mayores que el valor del nodo). Se te dan, además, los enteros $c_1, \ldots, c_n$, que son cuántas veces va a ser accedido cada elemento, y el objetivo es minimizar la suma de los costes de todos los accesos, donde el coste de un acceso es la profundidad del nodo al que se accede.
Está claro que los valores $a_1, \ldots, a_n$ son irrelevantes para el problema y que sólo son importantes $n$ y los $c_i$. Notemos que el problema tiene la siguiente estructura recursiva: una vez escogemos la raíz del árbol, el árbol binario óptimo con esa raíz se constituye de formar los árboles binarios óptimos con los valores menores y mayores que la raíz en los hijos izquierdo y derecho de la raíz respectivamente. Por tanto, si denotamos por $f(l, r)$ el coste de calcular el árbol binario mínimo para los valores $a_l, \ldots, a_r$, tenemos la siguiente recurrencia:
$$
f(l, r) = \min_{l \leq i \leq r} \left(f(l, i-1) + f(i+1, r)\right) + \sum_{i=l}^r c_i
$$
Esto nos proporciona una solución con programación dinámica de complejidad $O(n^4)$, que se puede mejorar muy fácilmente a $O(n^3)$ precalculando las sumas cumulativas de $c$.
Sin embargo, el problema se puede solucionar en tiempo $O(n^2)$. Veamos cómo. Sea $i^*(l, r) = \text{arg min}_{l \leq i \leq r} \left(f(l, i-1) + f(i+1, r)\right)$, es decir, el $i$ óptimo escogido (en caso de empate en el valor de la expresión, cogemos el mayor $i$). La clave está en que se satisface la siguiente desigualdad: $i^*(l, r-1) \leq i^*(l, r) \leq i^*(l+1, r)$. Esto fue demostrado por D. Knuth usando argumentos específicos para el problema de los árboles binarios óptimos, pero F. Yao demostró que en general la propiedad se satisface para cualquier recurrencia del tipo:
$$f(l, r) = \min_{l \leq i \leq r} \left(f(l, i-1) + f(i+1, r)\right) + C(l, r)$$
Donde $C(l, r)$ satisface las siguientes dos propiedades, para todo $a \leq b \leq c \leq d$:
- Monotonicidad: $C(b, c) \leq C(a, d)$.
- Desigualdad cuadrangular: $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$.
Ver Yao 1980 para la demostración.
Una vez tenemos esta propiedad de que $i^*(l, r-1) \leq i^*(l, r) \leq i^*(l+1, r)$, podemos resolver el problema en $O(n^2)$ de la siguiente forma: vamos calculando los valores $f(l, r)$ en orden creciente de $d = r-l$, y también calculamos los valores de $i^*(l, r)$. Para calcular $f(l, r)$ sólo hemos de iterar desde $i^*(l, r-1)$ hasta $i^*(l+1, r)$, por tanto para un valor fijo de $d$, el número de iteraciones totales para calcular todos los valores de $f(l, l+d)$ será $O(n)$, por tanto el coste total de calcular todos los valores es $O(n^2)$. Pseudocódigo:
initialize f(i, i) for all i
for d = 1 ... n-1
for l = 0 ... n-d-1
for i = i_opt(l, l+d-1) ... i_opt(l+1, l+d)
cost = f(l, i-1) + f(i+1, l+d) + C(l, l+d)
if (cost <= f(l, l+d))
f(l, l+d) = cost
i_opt(l, l+d) = i
Optimización "Divide y Vencerás"
La idea de que "el óptimo es monótono" que hemos visto en la optimización de Knuth se puede utilizar para optimizar la programación dinámica en muchos contextos. Aquí presentamos otro caso más en el que se puede aprovechar esta idea:
Supongamos que tenemos una recurrencia de la forma:
$$
f(i, j) = \min_{0 \leq k < j} (f(i-1, k) + C(j, k))
$$
Para $0 \leq i < n, 0 \leq j < m$, e, igual que antes, $C(j, k)$ se puede calcular en $O(1)$. Esto da lugar a una solución $O(nm^2)$; veamos cómo optimizarla si tenemos otra vez que $k^*(i, j) \leq k^*(i, j+1)$.
Calculemos el valor de $f\left(i, \left\lfloor \frac{m}{2} \right\rfloor \right)$ (y de $k^*\left(i, \left\lfloor \frac{m}{2} \right\rfloor \right)$) en $O(m)$. Ahora, notemos que para los valores de $j < \left\lfloor \frac{m}{2} \right\rfloor$, el óptimo será menor, y para los otros valores el óptimo será mayor. Por tanto, ahora para calcular $f(i, j)$ para $j < \left\lfloor \frac{m}{2} \right\rfloor$ sólo tenemos que iterar hasta $k^*\left(i, \left\lfloor \frac{m}{2} \right\rfloor \right)$), y para $j > \left\lfloor \frac{m}{2} \right\rfloor$ tenemos que iterar desde $k^*\left(i, \left\lfloor \frac{m}{2} \right\rfloor \right)$. Podemos seguir subdividiendo los intervalos en partes iguales y, teniendo en cuenta que el coste en cada nivel de recursividad es $O(m)$, el coste total será $O(m \log m)$ (esto es un argumento parecido al análisis del coste de la ordenación por fusión). En total, hemos optimizado nuestra programación dinámica a $O(nm \log m)$.
Fusión de pequeño a grande
En el manual de unión-búsqueda, uno de los ejercicios era demostrar que uniendo los conjuntos "de pequeño a grande", es decir, asignando como nodo representante el nodo representante del conjunto con mayor número de elementos, hacía que las complejidad de las consultas de encontrar el representante de un conjunto fuese como mucho $O(\log n)$. Para que quede más claro, damos aquí una explicación de por qué es eso:
Demostraremos, más generalmente, que si un conjunto en algún momento tiene profundidad $h$ (es decir, el árbol generado por los nodos del conjunto en la representación de la estructura unión-búsqueda tiene profundidado $h$), entonces el conjunto tiene al menos $2^{h-1}$ elementos. Lo demostraremos por inducción en $h$. Para $h = 1$, no hay nada que decir. Para $h > 1$, supongamos que es cierto para $h-1$. Sea $u$ el elemento representante de nuestro conjunto y consideremos uno de los subárboles con altura $h-1$: por inducción, este subárbol tiene al menos $2^{h-2}$ vértices. Notemos que, por cómo funciona unión-búsqueda con unión de pequeño a grande, el número de vértices de este subárbol no cambia desde que se unió al conjunto de $u$, por tanto en el momento de unirse tenía el mismo número de vértices. Y, como cuando se unió a $u$ el conjunto de $u$ tenía un número mayor o igual de elementos, el conjunto total después de la unión tiene al menos $2^{h-2}+2^{h-2} = 2^{h-1}$, tal como queríamos ver.
Esta idea no sólo sirve para la estructura unión-búsqueda. También es útil en problemas de árboles donde tenemos que calcular para cada vértice información sobre su subárbol, o donde en cada vértice tenemos que calcular recursivamente alguna cosa "fusionando" las respuestas de los hijos. Consideremos el siguiente problema como ejemplo: tenemos un árbol enraízado, en cada vértice hay un número, queremos saber para cada vértice cuántos números distintos hay en su subárbol correspondiente.
Una forma fácil de resolver ese problema es mateniendo en cada vértice el conjunto de números de su subárbol: este conjunto se calcula recursivamente, calculando los conjuntos de los hijos primero y calculando el del padre añadiendo todos los elementos de los de los hijos y añadiendo el número del padre. Si usamos std::set, la complejidad es $O(n^2 \log n)$.
Esta solución se puede modificar de forma sencilla para obtener una solución $O(n \left(\log n \right)^2)$: en lugar de en cada vértice padre crear un nuevo conjunto y "fusionar" todos los conjuntos de los hijos en ese nuevo conjunto, lo que hacemos es "pasar" el conjunto más grande de entre los hijos al padre (ojo: pasar por referencia, sin hacer una copia), y "fusionar" el resto de conjuntos de los hijos con ese conjunto. La razón por la que la complejidad es $O(n \left(\log n \right)^2)$ es por un argumento similar al de la complejidad del Union-Find: podemos deducir que cada número "es insertado" en un conjunto como mucho $O(\log n)$ veces, por tanto el número total de inserciones es $O(n \log n)$.
Complejidad de DPs sobre árboles
En la sección anterior, hemos visto que si tenemos un problema de árboles en el que tenemos que calcular una lista de valores en cada nodo a partir de "fusionar" las listas de los hijos, "fusionar" las dos listas de valores de tamaño $a, b$ se puede hacer en $O(\min(a, b))$, y las hojas tienen listas de tamaño $1$, entonces podemos calcular todas las listas con complejidad $O(n \log n)$. Pero otra situación que puede darse es que la "fusión" de las listas tenga complejidad $O(a+b)$ o $O(a \cdot b)$. Esto se da sobre todo en problemas de programación dinámica en los que tenemos un código como el siguiente:
calcular_dp (u):
dp[u] = inicializar_vector(1)
dp[u][0] = valor_inicial[u]
por cada hijo v de u:
calcular_dp(v)
new_dp = inicializar_vector(longitud(dp[v])+longitud(dp[u]))
por cada i = 0 ... longitud(dp[u])
por cada j = 0 ... longitud(dp[v])
new_dp[i+j] = calcular_algo(dp[u][i], dp[v][j])
dp[u] = copiar_vector(new_dp)
En este caso, no podemos aplicar la técnica de fusión de pequeño a grande. Pero pasa una cosa muy interesante: aunque un análisis superficial de la complejidad del código anterior daría como resultado $O(n^4)$ o $O(n^3)$, ¡en realidad la complejidad es $O(n^2)$!. Esto se puede demostrar por inducción, pero en este post de Codeforces se da una explicación más "visual".
$\textit{DP of connected components}$
El objetivo de este DP es contar el número de permutaciones que satisfacen una serie de restricciones en tiempo polinomial, por ejemplo, el número de permutaciones que satisfacen que no existe un índice $i$ tal que $p_i$ $<$ $p_{i+1}$ $<$ $p_{i+2}$.
La idea básica de este DP es considerar un vector de tamaño $n$ inicialmente vacio, al que iremos añadiendo los elementos $\textbf{ordenadamente}$ hasta generar una permutación. Por ejemplo, si tenemos que $n$ = 6, el vector incial lo podemos representar como (?, ?, ?, ?, ?, ?) y por ejemplo añadir los elementos de la siguiente forma: $(?, ?, ?, ?, ?, ?)$ $\rightarrow$ $(?, ?, ?, 1, ?, ?)$ $\rightarrow$ $(?, 2, 1, ?, ?, ?)$ $\rightarrow$ $(?, 2, 1, ?, 3, ?)$ $\rightarrow$ $(?, 2, 1, ?, 3, 4)$ $\rightarrow$ $(5, 2, 1, ?, 3, 4)$ - $(5, 2, 1, 6, 3, 4)$. Aunque existen $n!$ vectores posibles, los agruparemos de una forma inteligente para nuestro proposito, en concreto nos interesará cuál es el último elemento que hemos añadido y cuantos componentes conexos tiene el vector, donde definimos número de componentes conexos como número de grupos continuos. Por ejemplo, el vector (1, 3, ?, 2) iría en el grupo (3, 2), ya que el último elemento que añadimos fue el 3 y tiene dos componentes conexos (el (1, 3) y el (2)), el vector (4, ?, 3, ?, 1, ?, 2) iría al grupo (4, 4), el (4, 1, 5, ?, 3, ?, 2) al grupo (5, 3).
Por tanto, $DP_{i, j}$ = #vectores donde se han colocado los elementos {1, ..., $i$} y que tienen $j$ componentes conexas.
Las transiciones suelen depender bastante del problema pero suelen ser similares al problema que propondremos a continuación.
$\textit{Problema 1}$: Calcular el número de permutaciones de $n$ (sin ninguna restricción).
Aunque podemos calcular $n!$ en $O$($n$), en este caso lo resolveremos en $O$($n^2$) con $\textit{DP of connected components}$ con el fin de explicar un ejemplo sencillo.
Los estados serán los ya explicados, $DP_{i, j}$ = #vectores donde se han colocado los elementos {1, ..., $n$} y que tienen $j$ componentes conexas. Ahora veamos cómo podemos añadir un nuevo elemento.
Si hemos añadido $i$ elementos y tenemos $j$ componentes podemos:
- Añadir el elemento $i+1$ al final de un componente, hay $j$ formas de hacerlo y el número de componentes no varía, por lo que $DP_{i, j}$ $\rightarrow$ $DP_{i+1, j}$ de $j$ formas diferentes ($DP_{i+1, j}$ += $j$*$DP_{i, j}$ cuando trabajamos con código).
- Añadir el elemento $i+1$ al principio de un componente, hay $j$ formas de hacerlo y el número de componentes no varía, por lo que $DP_{i, j}$ $\rightarrow$ $DP_{i+1, j}$ de otras $j$ formas diferentes ($DP_{i+1, j}$ += $j$*$DP_{i, j}$ cuando trabajamos con código).
- Añadir un nuevo componente, ya que los componentes están ordenados hay $j+1$ formas de crear un nuevo componente (entre 2 componentes ya existentes, de $j-1$ formas, al principio o al final), $DP_{i, j}$ $\rightarrow$ $DP_{i+1, j+1}$.
- Unir dos componentes contiguos, hay $j-1$ formas de hacerlo, $DP_{i, j}$ $\rightarrow$ $DP_{i+1, j-1}$.
Por último, nuestra permutación final debe tener solo un componente, por lo que el número de permutaciones de $n$ es $DP_{n, 1}$.
Otra forma de pensar en los vectores de manera intuitiva, es usar conjuntos ordenados de conjuntos ordenados, por ejemplo expresar el vector (4, ?, 3, 1, ?, 2, ?) como {{4}, {3, 1}, {2}} ya que las posiciones realmente no están "fijas", solo fijamos los el número de componentes.
Añadir nuevo comentario