Introducción a Programación Dinámica

¿Qué es programación dinámica?

Analogía: Imagina que te preguntan: "¿Cuánto es 3+5+2+7+1+4?". Calculas: 22. Luego te preguntan: "¿Y si le sumas 6?". No vuelves a sumar todo — usas el resultado anterior: 22 + 6 = 28. ¡Eso es programación dinámica! Guardar resultados para no recalcularlos.

Formalmente, DP se aplica cuando un problema tiene:

1. Subestructura óptima: La solución óptima se construye a partir de soluciones óptimas de subproblemas.
2. Subproblemas superpuestos: Los mismos subproblemas se resuelven múltiples veces.

Ejemplo clásico: Fibonacci

Sin DP ($O(2^n)$, ¡terrible!):

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

Top-Down (Memoización)

Recursión + guardar resultados:

long long memo[105];
bool calculado[105];

long long fib(int n) {
    if (n <= 1) return n;
    if (calculado[n]) return memo[n];

    calculado[n] = true;
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

Bottom-Up (Tabulación)

Llenar una tabla iterativamente:

long long fib(int n) {
    long long dp[105];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

Ambos son $O(n)$.

Los 4 pasos para resolver con DP

Problema clásico: Monedas

Dado un conjunto de monedas, ¿cuál es el mínimo número de monedas para dar cambio de una cantidad C?

Monedas: {1, 5, 10, 25}
Cantidad: 36
Respuesta: 3 (25 + 10 + 1)

Paso 1 — Estado: dp[c] = mínimo de monedas para la cantidad c.

Paso 2 — Transición: Para cada moneda m, si c >= m, entonces dp[c] = min(dp[c], dp[c - m] + 1).

Paso 3 — Caso base: dp[0] = 0 (0 monedas para dar cambio de 0).

Paso 4 — Respuesta: dp[C].

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n, C;
    cin >> n >> C;

    vector<int> monedas(n);
    for (int &m : monedas) cin >> m;

    vector<int> dp(C + 1, INT_MAX);
    dp[0] = 0;

    for (int c = 1; c <= C; c++) {
        for (int m : monedas) {
            if (c >= m && dp[c - m] != INT_MAX) {
                dp[c] = min(dp[c], dp[c - m] + 1);
            }
        }
    }

    cout << (dp[C] == INT_MAX ? -1 : dp[C]) << endl;

    return 0;
}

Problema: Subsecuencia creciente más larga (LIS)

Dada una secuencia, encuentra la subsecuencia creciente más larga.

Secuencia: [10, 9, 2, 5, 3, 7, 101, 18]
LIS: [2, 3, 7, 18] → longitud 4

Estado: dp[i] = longitud de la LIS que termina en i.

Transición: dp[i] = max(dp[j] + 1) para todo j < i donde v[j] < v[i].

int lis(vector<int> &v) {
    int n = v.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

$O(n^2)$. Existe una versión $O(n \log n)$ con búsqueda binaria.

Problema: Mochila 0/1

Tienes N objetos con peso y valor. Tu mochila aguanta un peso máximo W. ¿Cuál es el valor máximo que puedes cargar?

int knapsack(vector<int> &peso, vector<int> &valor, int W) {
    int n = peso.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];  // No tomar objeto i
            if (w >= peso[i-1]) {
                dp[i][w] = max(dp[i][w], dp[i-1][w - peso[i-1]] + valor[i-1]);
            }
        }
    }

    return dp[n][W];
}

Ejercicio de práctica

Sube una escalera de N escalones. En cada paso puedes subir 1 o 2 escalones. ¿De cuántas formas puedes llegar arriba?

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long dp[105];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;
    return 0;
}