Para clarificar, se distingue entre un DP interno con arreglo f y un DP externo con arreglo F.

Problema BZOJ3864：Encuentro entre Héroes

Este problema se trasladó a la plataforma LuoGu. Sirve como ejemplo clásico para esta técnica.

Enunciado

Dada una cadena S con un alfabeto compuesto por los caracteres ACGT. Se define LCS(S, T) como la longitud de la subsecuencia común más larga entre S y T.

Para cada 0 ≤ i ≤ |S|, se debe calcular cuántas cadenas T de longitud m con el mismo alfabeto satisfacen |LCS(S, T)| = i. El resultado se toma módulo 10^9 + 7.

Se tienen las restricciones: 1 ≤ T ≤ 5, 1 ≤ |S| ≤ 15, y 1 ≤ m ≤ 1000.

Enfoque

La idea fundamental del DP sobre DP es codificar la información del DP interno en los índices del DP externo. Durante las transiciones del DP externo, se itera sobre estos índices y se aplica una función que simula las transiciones del DP interno.

En este caso, se considera el proceso para calcular el LCS. Para cada posición i en T y j en S, se actualizan los valores. Esto se puede modelar con una función trans que, dado el carácter actual de T y el estado del DP interno, produce el nuevo estado.

Matemáticamente:

La compresión del arreglo se basa en la observación de que los valores f_{i,1} a f_{i,|S|} son monótonos no decrecientes y la diferencia entre elementos adyacentes es a lo sumo 1. Por lo tanto, se puede representar como una máscara binaria usando diferencias.

La estructura del código se establece así: se itera externamente por i y T_i, con transiciones:

La complejidad inicial sería O(m × |alfabeto| × 2^{|S|} × |S|), lo cual es alto. Sin embargo, dado que para parámetros T_i y mask fijos, trans(T_i,mask) es el mismo, se puede precomputar todas las transiciones posibles. Esto reduce la complejidad a O(|alfabeto| × 2^{|S|} × |S| + m × |alfabeto| × 2^{|S|}), lo cual es factible.

Código (reestructurado)

#include <bits/stdc++.h>
using namespace std;
const int MAX_LONG = 1005, MAX_LEN = 20, MAX_MASCARA = (1 << 15) + 5, MODULO = 1e9 + 7;
char conjunto[] = {"ACGT"};
int transiciones[MAX_MASCARA][4];
int dpEstado[2][MAX_MASCARA];
int respuestas[MAX_LEN];
char cadena[MAX_LEN];
int longitud, tamCadena;

inline int sumarMod(int a, int b) {
    int res = a + b;
    return res >= MODULO ? res - MODULO : res;
}

void acumular(int &destino, int valor) {
    destino = sumarMod(destino, valor);
}

int calcularTransicion(int mascara, char caracter) {
    int dpPrevio[MAX_LEN] = {0}, dpActual[MAX_LEN] = {0};
    for (int idx = 1; idx <= tamCadena; idx++) {
        dpPrevio[idx] = dpPrevio[idx - 1] + ((mascara >> (idx - 1)) & 1);
    }
    for (int idx = 1; idx <= tamCadena; idx++) {
        dpActual[idx] = max(dpPrevio[idx], dpActual[idx - 1]);
        if (caracter == cadena[idx]) {
            dpActual[idx] = max(dpActual[idx], dpPrevio[idx - 1] + 1);
        }
    }
    int nuevaMascara = 0;
    for (int idx = 1; idx <= tamCadena; idx++) {
        int diferencia = dpActual[idx] - dpActual[idx - 1];
        nuevaMascara |= (diferencia << (idx - 1));
    }
    return nuevaMascara;
}

void resolver() {
    scanf("%s%d", cadena + 1, &longitud);
    tamCadena = strlen(cadena + 1);
    for (int mascara = 0; mascara < (1 << tamCadena); mascara++) {
        for (int k = 0; k < 4; k++) {
            transiciones[mascara][k] = calcularTransicion(mascara, conjunto[k]);
        }
    }
    int estadoActual = 0, estadoAnterior = 1;
    memset(dpEstado, 0, sizeof(dpEstado));
    dpEstado[estadoActual][0] = 1;
    for (int paso = 1; paso <= longitud; paso++) {
        swap(estadoActual, estadoAnterior);
        memset(dpEstado[estadoActual], 0, sizeof(dpEstado[estadoActual]));
        for (int k = 0; k < 4; k++) {
            for (int mascara = 0; mascara < (1 << tamCadena); mascara++) {
                int nueva = transiciones[mascara][k];
                acumular(dpEstado[estadoActual][nueva], dpEstado[estadoAnterior][mascara]);
            }
        }
    }
    memset(respuestas, 0, sizeof(respuestas));
    for (int mascara = 0; mascara < (1 << tamCadena); mascara++) {
        int bits = __builtin_popcount(mascara);
        acumular(respuestas[bits], dpEstado[estadoActual][mascara]);
    }
    for (int i = 0; i <= tamCadena; i++) {
        printf("%d\n", respuestas[i]);
    }
}

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        resolver();
    }
    return 0;
}

Problema TJOI2018：Fiesta en el Jardín

Similar al anterior, pero con la restricción de que la cadena generada no puede contener la subcadena NOI. Se añade una dimensión adicional en F para representar las tres fases del patrón prohibido.

Código (reestructurado)

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1005, MAX_M = 20, MAX_MASK = (1 << 15) + 5, MOD = 1e9 + 7;
char alfabeto[] = {"NOI"};
int tablaTrans[MAX_MASK][3];
int dp[2][4][MAX_MASK];
int resultado[MAX_M];
char pat[MAX_M];
int n, m;

inline int sumaMod(int x, int y) {
    return x + y >= MOD ? x + y - MOD : x + y;
}

void agregar(int &dest, int val) {
    dest = sumaMod(dest, val);
}

int calcTrans(int mask, char c) {
    int previo[MAX_M] = {0}, actual[MAX_M] = {0};
    for (int i = 1; i <= m; i++) {
        previo[i] = previo[i - 1] + ((mask >> (i - 1)) & 1);
    }
    for (int i = 1; i <= m; i++) {
        actual[i] = max(previo[i], actual[i - 1]);
        if (c == pat[i]) {
            actual[i] = max(actual[i], previo[i - 1] + 1);
        }
    }
    int nueva = 0;
    for (int i = 1; i <= m; i++) {
        nueva += (actual[i] - actual[i - 1]) << (i - 1);
    }
    return nueva;
}

int main() {
    cin >> n >> m;
    scanf("%s", pat + 1);
    for (int mask = 0; mask < (1 << m); mask++) {
        for (int k = 0; k < 3; k++) {
            tablaTrans[mask][k] = calcTrans(mask, alfabeto[k]);
        }
    }
    int cur = 0, prev = 1;
    dp[cur][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        swap(cur, prev);
        memset(dp[cur], 0, sizeof(dp[cur]));
        for (int k = 0; k < 3; k++) {
            int siguiente = k + 1;
            int anterior = k;
            int destino = k == 0 ? 1 : 0;
            for (int fase = 0; fase < 3; fase++) {
                int nuevaFase = (fase == anterior) ? siguiente : destino;
                for (int mask = 0; mask < (1 << m); mask++) {
                    agregar(dp[cur][nuevaFase][tablaTrans[mask][k]], dp[prev][fase][mask]);
                }
            }
        }
    }
    memset(resultado, 0, sizeof(resultado));
    for (int fase = 0; fase < 3; fase++) {
        for (int mask = 0; mask < (1 << m); mask++) {
            agregar(resultado[__builtin_popcount(mask)], dp[cur][fase][mask]);
        }
    }
    for (int i = 0; i <= m; i++) {
        printf("%d\n", resultado[i]);
    }
    return 0;
}

Problema ZJOI2019：Mahjong

Este es un problema avanzado recomendado por un senior, que involucra DP sobre DP con mayor complejidad. Se deja como ejercicio para el lector.