Problema 1: Subsecuencia Común Más Larga

Enunciado

Dadas dos cadenas de texto text1 y text2, determina la longitud de la subsecuencia común más larga entre ambas. Una subsecuencia se define como una nueva cadena generada a partir de la original mediante la eliminación de ciertos caracteres, respetando el orden relativo de los caracteres restantes. Por ejemplo, "ace" es una subsecuencia de "abcde", mientras que "aec" no lo es.

Este problema se resuelve eficientemente utilizando programación dinámica, donde construimos una tabla que almacena las longitudes de las subsecuencias comunes para todos los prefijos posibles de ambas cadenas.

Solución Implementada

class Solucion {
public:
    int longestCommonSubsequence(string cadenaA, string cadenaB) {
        // tabla[i][j]: longitud de la subsecuencia común más larga
        // considerando los primeros i caracteres de cadenaA
        // y los primeros j caracteres de cadenaB
        vector<vector>> tabla(cadenaA.size() + 1, 
                                  vector<int>(cadenaB.size() + 1, 0));
        
        for(size_t i = 1; i <= cadenaA.size(); ++i) {
            for(size_t j = 1; j <= cadenaB.size(); ++j) {
                if(cadenaA[i - 1] == cadenaB[j - 1]) {
                    tabla[i][j] = tabla[i - 1][j - 1] + 1;
                } else {
                    tabla[i][j] = max(tabla[i - 1][j], tabla[i][j - 1]);
                }
            }
        }
        return tabla[cadenaA.size()][cadenaB.size()];
    }
};
</int></vector>

Problema 2: Líneas que No se Cruzan

Enunciado

Se tienen dos líneas horizontales paralelas. En la primera línea se escribe una secuencia de números nums1, y en la segunda línea se escribe nums2, ambos en orden ascendente de izquierda a derecha. Se desea conectar algunos pares de números iguales con líneas rectas, cumpliendo las siguientes restricciones: cada número puede pertenecer a exactamente una línea de conexión, y ninguna línea puede cruzar otra línea existente.

La clave para resolver este problema es reconocer que encontrar el máximo número de líneas que no se cruzan es equivalente a encontrar la longitud de la subsecuencia común más larga entre nums1 y nums2.

Solución Implementada

class Solucion {
public:
    int maxUncrossedLines(vector<int>& secuenciaA, vector<int>& secuenciaB) {
        vector<vector>> tabla(secuenciaA.size() + 1,
                                  vector<int>(secuenciaB.size() + 1, 0));
        
        for(size_t i = 1; i <= secuenciaA.size(); ++i) {
            for(size_t j = 1; j <= secuenciaB.size(); ++j) {
                if(secuenciaA[i - 1] == secuenciaB[j - 1]) {
                    tabla[i][j] = tabla[i - 1][j - 1] + 1;
                } else {
                    tabla[i][j] = max(tabla[i - 1][j], tabla[i][j - 1]);
                }
            }
        }
        return tabla[secuenciaA.size()][secuenciaB.size()];
    }
};
</int></vector></int></int>

Problema 3: Subarreglo Contiguo con Suma Máxima ### Enunciado

Dado un arreglo de enteros nums, se debe encontrar el subarreglo contiguo (que contiene al menos un elemento) cuya suma sea la máxima posible, y retornar dicha suma. Un subarreglo se define como una porción continua del arreglo original.

Este es un problema clásico que puede resolverse en una sola pasada utilizando programación dinámica. La idea principal es determinar, para cada posición, cuál es la suma máxima de un subarreglo que termina en esa posición específica.

Solución Implementada

class Solucion {
public:
    int maxSubArray(vector<int>& numeros) {
        // tabla[i]: suma máxima del subarreglo contiguo que termina en el índice i
        vector<int> tabla(numeros.size(), 0);
        
        if(numeros.size() == 1) {
            return numeros[0];
        }
        
        tabla[0] = numeros[0];
        int maximo = tabla[0];
        
        for(size_t i = 1; i < numeros.size(); ++i) {
            // Dos opciones: continuar el subarreglo anterior o iniciar uno nuevo
            tabla[i] = max(tabla[i - 1] + numeros[i], numeros[i]);
            maximo = max(maximo, tabla[i]);
        }
        return maximo;
    }
};
</int></int>

Los tres problemas presentados demuestran la potencia de la programación dinámica como técnica de resolución. El primer y segundo problema son esencialmente equivalentes, mientras que el tercero ilustra cómo optimizar el espacio cuando solo necesitamos referringnos al estado anterior.