Modelo del Triángulo Numérico

El problema del triángulo numérico consiste en encontrar la ruta de suma máxima (o mínima) desde la cima hasta la base de un triángulo de números, donde en cada paso solo se puede mover a los números adyacentes en la fila inferior. Este es un ejemplo introductorio clásico de la programación dinámica lineal.

Enfoque de Arriba hacia Abajo

En esta estrategia, calculamos la suma máxima acumulada desde el vértice superior hacia la base. Un detalle crucial en la implementación es la inicialización de los bordes con valores negativos infinitos para evitar que las transiciones desde posiciones inválidas afecten el resultado.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_FILAS = 510;
const int MENOS_INFINITO = -1e9;

int n;
int triangulo[MAX_FILAS][MAX_FILAS];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    // Inicialización de bordes para evitar transiciones inválidas
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= i + 1; ++j) {
            triangulo[i][j] = MENOS_INFINITO;
        }
    }

    cin >> triangulo[1][1];
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            int valor;
            cin >> valor;
            triangulo[i][j] = valor + max(triangulo[i - 1][j - 1], triangulo[i - 1][j]);
        }
    }

    int suma_maxima = MENOS_INFINITO;
    for (int j = 1; j <= n; ++j) {
        suma_maxima = max(suma_maxima, triangulo[n][j]);
    }

    cout << suma_maxima << "\n";
    return 0;
}

Enfoque de Abajo hacia Arriba

Este método es generalmente más elegante, ya que evita la complejidad de inicializar los bordes. Comenzamos desde la base del triángulo y ascendemos, actualizando cada celda con el máximo de sus dos hijos directos.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_FILAS = 510;

int n;
int triangulo[MAX_FILAS][MAX_FILAS];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
            
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> triangulo[i][j];
        }
    }
    
    // Ascendemos desde la penúltima fila hasta la cima
    for (int i = n - 1; i >= 1; --i) {
        for (int j = 1; j <= i; ++j) {
            triangulo[i][j] += max(triangulo[i + 1][j], triangulo[i + 1][j + 1]);
        }
    }
            
    cout << triangulo[1][1] << "\n";
    return 0;
}

Modelo de Subsecuencia Creciente Más Larga (LIS)

El problema de la Subsecuencia Creciente Más Larga (LIS, por sus siglas en inglés) busca la longitud de la subsecuencia estrictamente monotónica creciente más grande dentro de una secuencia dada.

LIS con Complejidad $O(N^2)$

Definimos el estado $dp[i]$ como la longitud de la subsecuencia creciente más larga que termina exactamente en el índice $i$. La transición evalúa todos los índicees anteriores $j < i$ donde el valor sea menor.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1010;

int n;
int secuencia[MAX_N], dp_lis[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> secuencia[i];
    }
    
    int longitud_global = 0;
    for (int i = 1; i <= n; ++i) {
        dp_lis[i] = 1; // La subsecuencia mínima es el elemento por sí solo
        for (int j = 1; j < i; ++j) {
            if (secuencia[j] < secuencia[i]) {
                dp_lis[i] = max(dp_lis[i], dp_lis[j] + 1);
            }
        }
        longitud_global = max(longitud_global, dp_lis[i]);
    }
        
    cout << longitud_global << "\n";
    return 0;
}

Extensión: Subsecuencia Ordenada Personalizada

El concepto de "creciente" puede generalizarse a cualquier orden predefinido. Si se proporciona una permutación específica que dicta el orden válido, podemos mapear cada elemento a su índice en esta permutación y aplicar la lógica estándar de LIS sobre estos nuevos índices.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_ELEMENTOS = 210;
const int MENOS_INFINITO = -1e9;

int orden_objetivo[MAX_ELEMENTOS];
int mapa_posiciones[MAX_ELEMENTOS];
int dp_custom[MAX_ELEMENTOS];

void resolver() {
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> orden_objetivo[i];
        mapa_posiciones[orden_objetivo[i]] = i;
    }

    int l;
    cin >> l;
    
    int resultado = MENOS_INFINITO;
    for (int i = 0; i < l; ++i) {
        int elemento;
        cin >> elemento;

        int mejor_previo = MENOS_INFINITO;
        // Buscamos el mejor precedente según el orden personalizado
        for (int j = 0; j <= mapa_posiciones[elemento]; ++j) {
            mejor_previo = max(mejor_previo, dp_custom[orden_objetivo[j]] + 1);
        }
        
        dp_custom[elemento] = mejor_previo;
        resultado = max(resultado, mejor_previo);
    }

    cout << resultado << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    resolver();
    return 0;
}

LIS con Complejidad $O(N \log N)$

Cuando $N$ aumenta hasta $10^5$, el enfoque $O(N^2)$ es insuficiente. Utilizamos un enfoque greedy combinado con búsqueda binaria. Mantneemos un arreglo auxiliar que almacena el valor final más pequeño posible para una subsecuencia de una longitud dada. Dado que los valores finales de las subsecuencias de longitudes crecientes son estrictamente monótonos, podemos usar búsqueda binaria para localizar la posición de inserción en tiempo logarítmico.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100010;

int n;
int elementos[MAX_N];
int colas_subsecuencias[MAX_N]; // colas_subsecuencias[i] guarda el menor valor final para una LIS de longitud i

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> elementos[i];
    }
    
    int longitud_actual = 0;
    for (int i = 1; i <= n; ++i) {
        // Búsqueda binaria para encontrar la mayor longitud cuya cola sea menor que elementos[i]
        int izquierda = 0, derecha = longitud_actual;
        while (izquierda < derecha) {
            int medio = izquierda + (derecha - izquierda + 1) / 2;
            if (colas_subsecuencias[medio] < elementos[i]) {
                izquierda = medio;
            } else {
                derecha = medio - 1;
            }
        }
        
        longitud_actual = max(longitud_actual, izquierda + 1);
        colas_subsecuencias[izquierda + 1] = elementos[i];
    }
    
    cout << longitud_actual << "\n";
    return 0;
}

Subsecuencia Común Más Larga (LCS)

El problema de la Subsecuencia Común Más Larga busca la longitud de la subsecuencia compartida más larga entre dos cadenas. Definimos $dp[i][j]$ como la LCS de los prefijos de longitud $i$ y $j$.

La transición se basa en si los caracteres actuales $str1[i]$ y $str2[j]$ coinciden. Si no coinciden, el estado hereda el máximo de excluir el carácter actual de la primera o de la segunda cadena. Si coinciden, se suma 1 al estado de los prefijos anteriores. Es importante notar que $dp[i-1][j]$ y $dp[i][j-1]$ cubren implícitamente los casos donde uno o ambos caracteres son excluidos, evitando la necesidad de evaluar $dp[i-1][j-1]$ por separado en la rama de no coincidencia.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAX_LON = 1010;

int lon1, lon2;
string str1, str2;
int matriz_lcs[MAX_LON][MAX_LON];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> lon1 >> lon2;
    cin >> str1 >> str2;
    
    // Ajuste de índices base 1 para las cadenas
    str1 = " " + str1;
    str2 = " " + str2;
    
    for (int i = 1; i <= lon1; ++i) {
        for (int j = 1; j <= lon2; ++j) {
            matriz_lcs[i][j] = max(matriz_lcs[i - 1][j], matriz_lcs[i][j - 1]);
            if (str1[i] == str2[j]) {
                matriz_lcs[i][j] = max(matriz_lcs[i][j], matriz_lcs[i - 1][j - 1] + 1);
            }
        }
    }
    
    cout << matriz_lcs[lon1][lon2] << "\n";
    return 0;
}

Distancia de Edición Mínima

Dadas dos cadenas, el objetivo es transformar la primera en la segunda utilizando el número mínimo de operaciones: inserción, eliminación o sustitución de caracteres. El estado $dp[i][j]$ representa el costo mínimo de transformar el prefijo de longitud $i$ de la cadena origen en el prefijo de longitud $j$ de la cadena destino.

Las transiciones evalúan la última operación realizada:

• Eliminar: El costo es $dp[i-1][j] + 1$.
• Insertar: El costo es $dp[i][j-1] + 1$.
• Sustituir (o mantener): Si los caracteres son iguales, el costo es $dp[i-1][j-1]$. Si son diferentes, el costo es $dp[i-1][j-1] + 1$.

La inicialización es crítica aquí: transformar una cadena de longitud $k$ en una vacía requiere $k$ eliminaciones, y viceversa. ```

#include #include #include

using namespace std;

const int MAX_LON = 1010;

int len_origen, len_destino; string src, dst; int dist_matriz[MAX_LON][MAX_LON];

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

cin >> len_origen >> src;
cin >> len_destino >> dst;

src = " " + src;
dst = " " + dst;

// Inicialización de casos base (transformar a/desde cadena vacía)
for (int i = 0; i <= len_destino; ++i) dist_matriz[0][i] = i;
for (int i = 0; i <= len_origen; ++i) dist_matriz[i][0] = i;

for (int i = 1; i <= len_origen; ++i) {
    for (int j = 1; j <= len_destino; ++j) {
        dist_matriz[i][j] = min(dist_matriz[i - 1][j] + 1, dist_matriz[i][j - 1] + 1);
        
        if (src[i] == dst[j]) {
            dist_matriz[i][j] = min(dist_matriz[i][j], dist_matriz[i - 1][j - 1]);
        } else {
            dist_matriz[i][j] = min(dist_matriz[i][j], dist_matriz[i - 1][j - 1] + 1);
        }
    }
}

cout << dist_matriz[len_origen][len_destino] << "\n";
return 0;

}