Patrones de Programación Dinámica

¿Por qué estudiar patrones?

Los problemas de DP parecen infinitos, pero en realidad la mayoría cae en unos pocos patrones. Si reconoces el patrón, ya tienes la mitad del problema resuelto.

Patrón 1: DP lineal

El estado depende solo de posiciones anteriores en un arreglo.

Subarreglo de suma máxima (Kadane)

int maxSubarraySum(vector<int> &v) {
    int n = v.size();
    int mejor = v[0];
    int actual = v[0];

    for (int i = 1; i < n; i++) {
        actual = max(v[i], actual + v[i]);
        mejor = max(mejor, actual);
    }

    return mejor;
}

Idea: actual es la mejor suma que termina en i. O empezamos de nuevo con v[i], o extendemos el subarreglo anterior.

Formas de llegar (con costos)

dp[i] = costo mínimo para llegar a la posición i, pudiendo avanzar 1 o 2 posiciones.

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

Patrón 2: DP en grids

Moverse en una cuadrícula, generalmente de esquina a esquina.

Caminos mínimos en grid

Grid:
1 3 1
1 5 1
4 2 1

Camino de menor costo de (0,0) a (n-1,m-1)
moviendo solo derecha o abajo.

int minPath(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));

    dp[0][0] = grid[0][0];

    // Primera fila: solo puedes venir de la izquierda
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    // Primera columna: solo puedes venir de arriba
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    // Resto: vienes de arriba o de la izquierda
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[n-1][m-1];
}

Contar caminos en grid

long long contarCaminos(int n, int m) {
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // Toda la primera fila y columna tiene 1 camino
    for (int j = 0; j < m; j++) dp[0][j] = 1;
    for (int i = 0; i < n; i++) dp[i][0] = 1;

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

    return dp[n-1][m-1];
}

Patrón 3: DP de subsecuencia

Comparar dos secuencias o encontrar propiedades en una.

Subsecuencia común más larga (LCS)

A = "ABCBDAB"
B = "BDCAB"
LCS = "BCAB" → longitud 4

Estado: dp[i][j] = longitud de LCS de A[0..i-1] y B[0..j-1].

int lcs(string &a, string &b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[n][m];
}

Distancia de edición (Edit Distance)

¿Cuántas operaciones (insertar, eliminar, reemplazar) para convertir A en B?

int editDist(string &a, string &b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    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 (a[i-1] == b[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]    // Reemplazar
                });
            }
        }
    }

    return dp[n][m];
}

Patrón 4: DP de intervalos

El estado es un rango [l, r] y probamos todos los puntos de corte.

Costo mínimo de multiplicación de matrices

Dada una cadena de matrices, ¿en qué orden multiplicarlas para minimizar operaciones?

int matrixChain(vector<int> &dims) {
    int n = dims.size() - 1;  // n matrices
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // len = longitud del intervalo
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            // Probar cada punto de corte k
            for (int k = i; k < j; k++) {
                int costo = dp[i][k] + dp[k+1][j]
                          + dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = min(dp[i][j], costo);
            }
        }
    }

    return dp[0][n-1];
}

Patrón 5: DP con bitmask

Cuando N es pequeño (≤ 20), puedes representar subconjuntos como bits.

Problema del viajero (TSP simplificado)

Visitar todas las ciudades exactamente una vez con costo mínimo.

int tsp(vector<vector<int>> &dist) {
    int n = dist.size();
    int FULL = (1 << n) - 1;

    // dp[mask][i] = costo mín para visitar las ciudades en mask,
    // estando actualmente en la ciudad i
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // Empezamos en ciudad 0

    for (int mask = 1; mask <= FULL; mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INT_MAX) continue;
            if (!(mask & (1 << u))) continue;

            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;  // Ya visitada

                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v],
                                     dp[mask][u] + dist[u][v]);
            }
        }
    }

    // Regresar a ciudad 0
    int ans = INT_MAX;
    for (int u = 0; u < n; u++) {
        if (dp[FULL][u] != INT_MAX) {
            ans = min(ans, dp[FULL][u] + dist[u][0]);
        }
    }

    return ans;
}

Patrón 6: DP de dígitos (Digit DP)

Contar números en un rango [0, N] que cumplen cierta propiedad.

Idea: Procesar dígito por dígito. El estado incluye:

• pos: dígito actual
• tight: ¿seguimos limitados por N?
• Información adicional del problema

string num;
int memo[20][2][200];  // [pos][tight][estado]

int solve(int pos, bool tight, int estado) {
    if (pos == num.size()) {
        return /* condición final */;
    }

    if (memo[pos][tight][estado] != -1)
        return memo[pos][tight][estado];

    int limite = tight ? (num[pos] - '0') : 9;
    int res = 0;

    for (int d = 0; d <= limite; d++) {
        res += solve(pos + 1,
                     tight && (d == limite),
                     /* nuevo estado */);
    }

    return memo[pos][tight][estado] = res;
}

Resumen de patrones

Ejercicio integrador

Dado un arreglo de enteros, encuentra la suma máxima de una subsecuencia donde no tomes dos elementos adyacentes.

Entrada: [3, 2, 7, 10]
Respuesta: 13 (3 + 10)

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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    if (n == 1) {
        cout << v[0] << endl;
        return 0;
    }

    vector<long long> dp(n);
    dp[0] = v[0];
    dp[1] = max(v[0], v[1]);

    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + v[i]);
        // No tomar i: dp[i-1]
        // Tomar i: dp[i-2] + v[i]
    }

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