CP-UPV Bootcamp - Capítulo 10

Capítulo 10: Programación dinámica

PROBLEMAS DEL CAPÍTULO

Para acceder a los problemas de este capítulo, accede con tu usuario y contraseña a cpupv.contest.codeforces.com. Si no tienes usuario y contraseña, inscríbete aquí.

Introducción

La programación dinámica es una de las estrategias más comunes de resolución de problemas en programación competitiva, principalmente debido a la eficiencia que puede llegar a proporcionar si es utilizada de manera correcta al aprovechar la superposición de subproblemas y las soluciones calculadas. Estos problemas, en general, buscan una optimización (camino más corto, forma más óptima de hacer x, etc.) y cumplen el principio de optimalidad, esto es, el problema posee una solución óptima que contiene soluciones óptimas para todas las sub-instancias de este problema.

Esto quiere decir que, si somos capaces de dividir de manera apropiada nuestro problema en pequeños sub-problemas y somos capaces de encontrar una solución eficiente a estos sub-problemas, y su relación con la solución del problema general, podemos solucionar aplicando programación dinámica nuestro problema.

Este tema es especialmente complicado, quizás el más difícil del bootcamp. Por eso requiere completar muchos problemas para entender bien el concepto.

Índice de Contenidos

Estrategias
- Top-down (Memoización)
- Bottom-up (Tabulación)
Ejemplos

Estrategias

Top-down (Memoización)

Basado en dirigirse primero a las sub-instancias del problema para después formar la solución del problema utilizando las soluciones previamente calculadas. Este enfoque es bastante usado en el contexto de la recursión, especialmente cuando dichas sub-instancias se solapan, ya que, si somos capaces de guardar las soluciones a medida que las vamos calculando, nos podemos ahorrar una parte considerable de los cálculos al no tener que calcular la solución de las sub-instancias solapadas, optimizando así el tiempo de ejecución.

En resumen: el enfoque top-down se basa en separar el problema en subproblemas, si el subproblema se ha resuelto, reutiliza la solución, en otro caso, resuelve el subproblema y almacena el resultado en memoria(generalmente, un array).

Es crucial tener en cuenta cuando diseñamos una solución con este enfoque el posible espacio adicional para las soluciones de los subproblemas y la definición de las sub-instancias.

Bottom-up (Tabulación)

A diferencia del enfoque Top-down, la tabulación actúa comenzando por el sub-problema más pequeño, para ir construyendo la solución final. Para ello, se irán guardando los resultados de los sub-problemas ya resueltos en una tabla, para así evitar cálculos redundantes que incrementarían el coste de nuestro algoritmo. Como podemos observar, ambos enfoques son similares en el hecho de almacenar soluciones para construir la solución, pero este segundo, por ejemplo, es mucho más activo y requiere de un paso adicional: elegir previamente el orden exacto en el que se realizarán los cálculos, ya que de otra forma esta estrategia no tendría efecto alguno. Además, este tipo de algoritmo suele implementarse generalmente de manera iterativa, ahorrando así los posibles problemas que nos pueda causar la recursividad.

Esta forma de afrontar un problema de programación dinámica suele estar más relacionada con problemas más complejos, que envuelvan operaciones más complicadas o que cuyas soluciones a los sub-problemas no se solapen.

Ejemplos

Qué mejor para entender cómo aplicar programación dinámica que varios ejemplos? Pasemos a ver unos cuantos de ellos:

Fibonacci

Primero de todo, veremos la implementación recursiva de este algoritmo, como ya sabemos, no es muy eficaz, y no nos podría servir en una competición de programación.

int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

Coste temporal $O(2^n)$

A continuación, utilizando memoización o tabulación, podemos crear dos implementaciones bastantes más eficientes que la anterior:

long long fib_mem(int n, vector<long long> &memo) {
    if (memo[n] != -1)
        return memo[n];
    if (n <= 1)
        memo[n] = n;
    else
        memo[n] = fib_mem(n - 1, memo) + fib_mem(n - 2, memo);
    return memo[n];
}

int main() {
    int n;
    cin >> n;
    vector<long long> memo(n + 1, -1);
    cout << fib_mem(n, memo);
}

Coste temporal $O(n)$
Coste espacial $O(n)$, debido a almacenar el vector y las llamadas recursivas

En esta ocasión, el enfoque top-down sería crear un array auxiliar que utilizaremos para ir guardando el valor del $i$-ésimo número de la secuencia de Fibonacci en su correspondiente casilla del array. De esta forma, podemos aprovechar ese solapamiento entre un número en la secuencia y sus dos anteriores para ahorrarnos cálculos innecesarios. Además, si guardamos las soluciones calculadas, en ciertos problemas podremos mejorar aún más la eficiencia del algoritmo, ya que para más queries, la solución ya estará calculada.

int fibonacci(int n) {
    if (n <= 1) return n;
    else {
        std::vector<int> table(n + 1, 0);
        table[0] = 0;
        table[1] = 1;
        for (int i = 2; i <= n; i++) {
            table[i] = table[i - 1] + table[i - 2];
        }
        return table[n];
    }
}

Si utilizamos la estrategia de tabulación, podemos llegar a la conclusión de que, si llenamos el array de manera iterativa, desde la posición 0 a la que consideremos necesaria, con los números de la secuencia de Fibonacci, calculados de la forma apropiada($a_n=a_{n-1}+a_{n-2}$), podemos tener construida una tabla(en este caso, un array), que tiene almacenadas las soluciones a todos los sub-problemas($n^{th}$ número de la secuencia).

Subsecuencia Común más Larga (Longest Common Subsequence)

Dadas dos strings, nuestra tarea es encontrar la subsecuencia común con la mayor longitud posible.

La subsecuencia común más larga (en inglés, Longest Common Subsequence, o LCS) entre dos secuencias ($a$ y $b$) es la subsecuencia más larga que aparece en ambos conjuntos de forma ordenada, pero no necesariamente consecutiva. Es decir, para dos arrays de elementos $a$ y $b$, eliminar el mínimo número de elementos cualesquiera de los arrays tal que $a = b$ y $longitud(a)$ sea máxima.

Por ejemplo:

string s1 = “ABCDEF”, s2 = "ACBDEF";
cout << longestCommonSubsequence(s1, s2);
> ABDEF o ACDEF

Una solución que se nos podría ocurrir sería comenzar por un extremo e ir comparando de manera recursiva hacia el otro extremo de los strings en búsqueda de esas subsecuencias y sus longitudes, pero eso podría conllevar costes demasiado elevados si las strings que nos proporcionan son de mayor longitud. La complejidad de este algoritmo sería de $O(2^{min(m,n)})$.

int lcs(string &S1, string &S2, int m, int n){
    // Caso base: una string está vacía
    if (m == 0 || n == 0)
        return 0;

    if (S1[m - 1] == S2[n - 1])
        // Incluir char en la cuenta y continuar recursivamente
        return 1 + lcs(S1, S2, m - 1, n - 1);

    else {
        // Si los dos últimos carácteres no concuerdan:
        // 1. Excluir el último carácter de S1
        // 2. Excluir el último carácter de S2 
        // Usar el maximo de ambas llamadas
        return max(lcs(S1, S2, m, n - 1), lcs(S1, S2, m - 1, n));
    }
}

int main() {
    string S1 = "AGGTAB";
    string S2 = "GXTXAYB";
    int m = S1.size();
    int n = S2.size();

    cout << lcs(S1, S2, m, n);

    return 0;
}

Coste temporal $O(2^{\min(m,n)})$

Por otra parte, si nos fijamos más en el problema, podemos darnos cuenta de que en ciertas ocasiones se pueden llegar a realizar comparaciones adicionales. Por ejemplo:

string s1 = "AXYT", s2 = "AYZX";

En este, se comprobaría el subproblema conformado por s1 = “AXY” y S2 = “AYZ” múltiples veces, cosa que no es eficiente. Entonces, sabiendo que las soluciones se solapan, podemos crear un array para almacenar esas posiciones:

// Devuelve longitud de subsecuencia
int lcs(string &S1, string &S2, int m, int n, vector<vector<int>> &memo) {

    // Caso Base
    if (m == 0 || n == 0)
        return 0;

    // Ya existe en la tabla
    if (memo[m][n] != -1)
        return memo[m][n];

    // Match
    if (S1[m - 1] == S2[n - 1])
        return memo[m][n] = 1 + lcs(S1, S2, m - 1, n - 1, memo);

    // No match
    return memo[m][n] = max(lcs(S1, S2, m, n - 1, memo), lcs(S1, S2, m - 1, n, memo));
}

int main() {
    string S1 = "AGGTAB";
    string S2 = "GXTXAYB";

    int m = S1.length();
    int n = S2.length();
    vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));

    cout << "Length of LCS is " << lcs(S1, S2, m, n, memo) << endl;

    return 0;
}

Coste temporal $O(m \times n)$
Coste espacial $O(m \times n)$

Otra forma de hacerlo es utilizando tabulación, podríamos crear un array vacío e ir llenando con el resultado de nuestros cálculos.

int lcs(string &S1, string &S2) {
    int m = S1.size();
    int n = S2.size();

    // Initializando tabla (m+1)*(n+1) con 0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Llenando tabla
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (S1[i - 1] == S2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // dp[m][n] contiene longitud de subsecuencia común más larga
    return dp[m][n];
}

int main() {
    string S1 = "AGGTAB";
    string S2 = "GXTXAYB";
    cout << "Length of LCS is " << lcs(S1, S2) << endl;

    return 0;
}

Coste temporal $O(m \times n)$
Coste espacial $O(m \times n)$

Subsecuencia Creciente más Larga (Longest Increasing Subsequence)

Basado en encontrar la secuencia creciente más larga en una lista, existen diversas formas de solucionar este problema, ya sea utilizando recursión, búsqueda binaria o programación dinámica.

La subsecuencia creciente más larga (en inglés, Longest Increasing Subsequence, o LIS) es la subsecuencia más larga en una secuencia de elementos que es estrictamente creciente. Es decir para una secuencia $a=[a_1, a_2, a_3, \dots, a_n]$ debemos quitar el mínimo número de elementos tal que $a$ sea creciente y su longitud sea la máxima.

Si la secuencia es: $a=[10,22,9,33,21,50,41,60,80]$, la subsecuencia creciente más larga es: $[10,22,33,50,60,80]$. La longitud de esta subsecuencia es $6$.

A diferencia de la subsecuencia común más larga (LCS), la subsecuencia creciente más larga se encuentra dentro de una sola secuencia.

Veamos un ejemplo de cómo podríamos hacerlo con solamente programación dinámica:

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1); // d[i] = longitud de LIS terminando en a[i]
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

Coste temporal $O(n^2)$
Coste espacial $O(n)$

Este ejemplo que utiliza memoización calcula usando un doble bucle la longitud de todas las subsecuencias crecientes, utilizando un array auxiliar que almacenará las longitudes que se calculen, para después buscar la mayor dentro del array. Pese a que es sencillo de implementar, no es tan eficiente como podríamos desear, teniendo un coste exponencial respecto al input. Por ello, debemos buscar una alternativa más eficiente, que puede ser, por ejemplo, utilizando una mezcla entre programación dinámica y búsqueda binaria:

Esta vez, el elemento del array auxiliar d[l] no corresponderá al elemento i del array ni a ningún prefijo, sino que será el elemento más pequeño en el que la subsecuencia creciente de longitud l termina, de esta forma, asignamos d[l] = a[i] solamente cuando no hay una secuencia creciente más larga que acabe en a[i], ni hay ninguna secuencia creciente de longitud l que acabe en un número más pequeño. La implementación de este algoritmo sería:

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    // d[i] almacena el mínimo último elemento de una subsecuencia 
    // de longitud i + 1
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

De esta forma, logramos conseguir optimizar el algoritmo y pasar de un coste exponencial a un coste linearitmico($O(n \log n)$).

Knapsack (El Algorítmo de la Mochila)

Para este problema, nos basaremos en el problema de 0/1 knapsack, que es la versión más básica del problema, existen otras cuyas soluciones se pueden obtener partiendo de la que obtenemos en este problema

Dados N elementos donde cada uno tiene un peso wt[i] y un valor asociado val[i], y dada una mochila con capacidad para un peso W, tenemos el objetivo de meter tantos elementos en la mochila como podamos, maximizando el valor que estos elementos tengan en total.

Podemos enfrentar este problema con un algoritmo recursivo que considere todos los subsets de elementos, calcular el peso y valor total de estos y comprobar de entre los que tengan peso menor a W, el que más valor tenga:

int knapSack(int W, int wt[], int val[], int n) {
    // Caso base
    if (n == 0 || W == 0)
        return 0;

    // Si el peso supera el límite, no incluir
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);

    // Devolver dependiendo de si añadimos o no el elemento
    else
        return max(knapSack(W, wt, val, n - 1), 
        val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1));
}

int main() {
    int profit[] = { 30, 180, 120 };
    int weight[] = { 90, 10, 60 };
    int W = 100;
    int n = sizeof(profit) / sizeof(profit[0]);
    cout << knapSack(W, weight, profit, n);
    return 0;
}

Este algoritmo tiene una complejidad temporal de $O(2^N)$, que no es lo que buscamos, por ende, intentemos solucionarlo de otra forma, tal vez mediante tabulación:

Crearemos una matriz en la que las columnas representan la capacidad de la mochila en orden ascendente, y las filas serán el índice del elemento que queremos añadir.

Imaginemos que tenemos tres elementos $e1: w=1, v=20, e2: w=2, v=15, e3: w=3, v=25$ y una mochila con una capacidad máxima de $3$.

	1	2	3
0	0	0	0
1	20	20	20
2	20	20	35
3	20	20	35

Debemos ordenar las filas por pesos de menor a mayor

LLenamos la matriz de la siguiente forma, para cada casilla de la matriz, comprobaremos cuál es el valor máximo que se puede almacenar, si cabe lo mismo que en la casilla anterior, o se puede añadir un elemento que sumando su valor nos da un valor mayor.

int knapSack_tab(int W, int wt[], int val[], int n) {
    // Crear una tabla de (n+1) x (W+1)
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // Construir la tabla de forma iterativa
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w)
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }

    // dp[n][W] contiene el valor máximo que se puede obtener
    return dp[n][W];
}

int main() {
    int profit[] = {30, 180, 120};
    int weight[] = {90, 10, 60};
    int W = 100;
    int n = sizeof(profit) / sizeof(profit[0]);
    cout << knapSack_tab(W, weight, profit, n);
    return 0;
}

Coste temporal $O(N \times W)$
Coste espacial $O(N \times W)$

Distancia de Levenshtein

La Distancia de Levenshtein (o edit distance) es el número mínimo de operaciones necesarias para transformar una cadena en otra. Las operaciones permitidas son:

Inserción de un carácter
Eliminación de un carácter
Sustitución de un carácter

Ejemplo:

Supongamos que queremos transformar la cadena cpupv en puppy. La distancia de Levenshtein es 3:

cpupv → pupv (eliminar 'c')
pupv → pupp (sustituir 'v' por 'p')
pupp → puppy (insertar 'y' al final)

		c	p	u	p	v
	0	1	2	3	4	5
p	1	1	1	2	3	4
u	2	2	2	1	2	3
p	3	3	2	2	1	2
p	4	4	3	3	2	2
y	5	5	4	4	3	3

int levenshtein(const string &s1, const string &s2) {
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({
                dp[i - 1][j],    // eliminar
                dp[i][j - 1],    // insertar
                dp[i - 1][j - 1] // sustituir
            });
        }
    }
    return dp[n][m];
}

Coste temporal: $O(m \times n)$, donde $m$ y $n$ son las longitudes de las cadenas.
Coste espacial: $O(m \times n)$.

Esta solución utiliza tabulación para calcular la distancia de forma eficiente, evitando recálculos innecesarios mediante el almacenamiento de subresultados en la matriz dp.