La programación dinámica dinámica (DDP) es una extensión de la programación dinámica clásica que permite actualizar los estados de transición de manera eficiente durante la ejecución. La idea central es representar las transiciones de DP como matrices, lo que facilita su manipulación y consulta rápida usando estructuras de datos como árboles de segmentos.

Problemas de Práctica

Los siguientes problemas ilustran el uso de DDP con matrices, ordenados por dificultad creciente:

• [HDU5068] Harry And Math Teacher: Un problema introductorio donde se aplican matrices de transciión con un árbol de segmentos.
• [CF1380F] Strange Addition: Requiere modelar la DP con matrices 3x3 para manejar estados complejos.
• [P5024 de Luogu] Defender el Reino: Un desafío avanzado que involucra DDP en árboles, aún en desarrollo.

Explicación Conceptual

El núcleo de DDP radica en utilizar matrices para codificar las ecuaciones de DP. Una vez que se formula la recurrencia, se puede representar como una multiplicación de matrices. Esto permite actualizaciones y consultas rápidas mediante árboles de segmentos, que mantienen el producto de matrices sobre rangos. La comprensión de la multiplicación de matrices es esencial para dominar esta técnica.

Implementación con Código

A continuación se presentan ejemplos en C++ que demuestran la aplicación práctica.

Ejemplo 1: Harry And Math Teacher

Este código usa un árbol de segmentos para mantener matrices de transición 2x2. Las operaciones de consulta y actualización se realizan con complejidad logarítmica.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

struct Matriz {
    int filas, columnas, datos[2][2];
    Matriz() { memset(datos, 0, sizeof(datos)); }
    Matriz operator * (const Matriz &otra) const {
        Matriz resultado;
        resultado.filas = filas;
        resultado.columnas = otra.columnas;
        for (int i = 0; i < filas; ++i) {
            for (int k = 0; k < columnas; ++k) {
                if (datos[i][k]) {
                    for (int j = 0; j < otra.columnas; ++j) {
                        resultado.datos[i][j] = (resultado.datos[i][j] + 1ll * datos[i][k] * otra.datos[k][j]) % MOD;
                    }
                }
            }
        }
        return resultado;
    }
    void establecerIdentidad() {
        filas = 2; columnas = 2;
        datos[0][0] = datos[1][1] = 1;
        datos[0][1] = datos[1][0] = 1;
    }
};

Matriz identidad, vectorInicial;

struct ArbolSegmentos {
    Matriz segmentos[MAXN * 4];
    void construir(int nodo, int izquierda, int derecha) {
        if (izquierda == derecha) {
            segmentos[nodo].establecerIdentidad();
            return;
        }
        int medio = (izquierda + derecha) / 2;
        construir(2 * nodo, izquierda, medio);
        construir(2 * nodo + 1, medio + 1, derecha);
        segmentos[nodo] = segmentos[2 * nodo] * segmentos[2 * nodo + 1];
    }
    void actualizar(int nodo, int izquierda, int derecha, int posicion, int fila, int columna) {
        if (izquierda == derecha) {
            segmentos[nodo].datos[fila][columna] ^= 1;
            return;
        }
        int medio = (izquierda + derecha) / 2;
        if (posicion <= medio) actualizar(2 * nodo, izquierda, medio, posicion, fila, columna);
        else actualizar(2 * nodo + 1, medio + 1, derecha, posicion, fila, columna);
        segmentos[nodo] = segmentos[2 * nodo] * segmentos[2 * nodo + 1];
    }
    Matriz consultar(int nodo, int izquierda, int derecha, int consultaL, int consultaR) {
        if (consultaL <= izquierda && derecha <= consultaR) return segmentos[nodo];
        int medio = (izquierda + derecha) / 2;
        Matriz resultado = identidad;
        if (consultaL <= medio) resultado = resultado * consultar(2 * nodo, izquierda, medio, consultaL, consultaR);
        if (medio + 1 <= consultaR) resultado = resultado * consultar(2 * nodo + 1, medio + 1, derecha, consultaL, consultaR);
        return resultado;
    }
} arbol;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    identidad.filas = identidad.columnas = 2;
    identidad.datos[0][0] = identidad.datos[1][1] = 1;
    vectorInicial.filas = 1;
    vectorInicial.columnas = 2;
    vectorInicial.datos[0][0] = vectorInicial.datos[0][1] = 1;
    int n;
    while (cin >> n) {
        arbol.construir(1, 1, n);
        int q;
        cin >> q;
        while (q--) {
            int tipo;
            cin >> tipo;
            if (tipo == 1) {
                int pos, fila, col;
                cin >> pos >> fila >> col;
                arbol.actualizar(1, 1, n, pos + 1, fila - 1, col - 1);
            } else {
                int l, r;
                cin >> l >> r;
                Matriz res = vectorInicial * arbol.consultar(1, 1, n, l + 1, r);
                cout << (res.datos[0][0] + res.datos[0][1]) % MOD << "\n";
            }
        }
    }
    return 0;
}

Ejemplo 2: Strange Addition

Este código utiliza matrices 3x3 para modelar la DP. La estructura del árbol de segmentos se adapta para manejar la multiplicación de matrices más grandes.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

struct Matriz {
    int filas, columnas, datos[3][3];
    Matriz() { memset(datos, 0, sizeof(datos)); }
    void configurarDesdeDigito(int digito) {
        filas = 3; columnas = 3;
        datos[0][0] = digito + 1; datos[0][1] = 9 - digito;
        datos[1][0] = (digito == 1) ? 1 : 0;
        datos[2][2] = 1;
    }
    Matriz operator * (const Matriz &otra) const {
        Matriz resultado;
        resultado.filas = filas;
        resultado.columnas = otra.columnas;
        for (int i = 0; i < filas; ++i) {
            for (int k = 0; k < columnas; ++k) {
                for (int j = 0; j < otra.columnas; ++j) {
                    resultado.datos[i][j] = (resultado.datos[i][j] + 1ll * datos[i][k] * otra.datos[k][j]) % MOD;
                }
            }
        }
        return resultado;
    }
};

int leerDigito() {
    char c;
    while (cin >> c && !isdigit(c));
    return c - '0';
}

struct ArbolSegmentos {
    Matriz segmentos[MAXN * 4];
    void combinar(int nodo) {
        segmentos[nodo] = segmentos[2 * nodo] * segmentos[2 * nodo + 1];
    }
    void construir(int nodo, int izquierda, int derecha) {
        if (izquierda == derecha) {
            segmentos[nodo].configurarDesdeDigito(leerDigito());
            return;
        }
        int medio = (izquierda + derecha) / 2;
        construir(2 * nodo + 1, medio + 1, derecha);
        construir(2 * nodo, izquierda, medio);
        combinar(nodo);
    }
    void modificar(int nodo, int izquierda, int derecha, int posicion, int nuevoValor) {
        if (izquierda == derecha) {
            segmentos[nodo].configurarDesdeDigito(nuevoValor);
            return;
        }
        int medio = (izquierda + derecha) / 2;
        if (posicion <= medio) modificar(2 * nodo, izquierda, medio, posicion, nuevoValor);
        else modificar(2 * nodo + 1, medio + 1, derecha, posicion, nuevoValor);
        combinar(nodo);
    }
} arbol;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    arbol.construir(1, 1, n);
    Matriz vectorEstado;
    vectorEstado.filas = 1;
    vectorEstado.columnas = 3;
    vectorEstado.datos[0][0] = 1;
    vectorEstado.datos[0][2] = 1;
    for (int consulta = 0; consulta < m; ++consulta) {
        int posicion, valor;
        cin >> posicion >> valor;
        arbol.modificar(1, 1, n, n - posicion + 1, valor);
        Matriz resultado = vectorEstado * arbol.segmentos[1];
        cout << resultado.datos[0][0] << "\n";
    }
    return 0;
}