Método sistemático para resolver problemas de DP
- Definir el arreglo DP y el significado de sus índices.
- Establecer la fórmula de recurrencia.
- Inicializar el arreglo DP.
- Determinar el orden de iteración.
- Depurar y verificar.
Problemas de introducción
1. Secuencia de Fibonacci
Enfoque: Definimos dp[i] como el i-ésimo término de la serie. La recurrencia es dp[i] = dp[i-1] + dp[i-2], con dp[0] = 0 y dp[1] = 1. Se itera en orden ascendente. Es importante manejar el caso n=0 por la inicialización.
class Solution {
public:
int fibonacci(int n) {
if (n == 0) return 0;
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int idx = 2; idx <= n; ++idx) {
dp[idx] = dp[idx - 1] + dp[idx - 2];
}
return dp[n];
}
};</int>
2. Escaleras
Enfoque: En cada paso se puede subir 1 o 2 escalones. Sea dp[i] el número de formas de llegar al escalón i. La recurrencia es dp[i] = dp[i-1] + dp[i-2], con dp[0] = 1 y dp[1] = 1. Se recorre en orden.
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int pos = 2; pos <= n; ++pos) {
dp[pos] = dp[pos - 1] + dp[pos - 2];
}
return dp[n];
}
};</int>
3. Escaleras con costo mínimo
Enfoque: Se puede empezar desde el escalón 0 o 1. Sea dp[i] el costo mínimo para llegar al escalón i. Recurrencia: dp[i] = min(dp[i-1] + costo[i-1], dp[i-2] + costo[i-2]), con dp[0] = 0 y dp[1] = 0. Iteración ascendente.
class Solution {
public:
int minCostClimbingStairs(vector<int>& costo) {
int total = costo.size();
vector<int> dp(total + 1);
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= total; ++i) {
dp[i] = min(dp[i - 1] + costo[i - 1], dp[i - 2] + costo[i - 2]);
}
return dp[total];
}
};</int></int>
4. Caminos únicos
Enfoque: Sea dp[i][j] el número de caminos hasta la celda (i, j). Recurrencia: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Inicialización: dp[0][1] = 1 y dp[1][0] = 1 para bordes. Se itera en orden.
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector>> dp(n + 1, vector<int>(m + 1, 0));
for (int a = 0; a <= n; ++a) dp[a][1] = 1;
for (int b = 0; b <= m; ++b) dp[1][b] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 2; j <= m; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[n][m];
}
};</int></vector>
5. Caminos con obstáculos
Enfoque: Similar al anterior, pero con obstáculos. Sea dp[i][j] los caminos hasta (i, j). Inicialización considera obstáculos en bordes. Recurrencia solo si no hay obstáculo: dp[i][j] = dp[i-1][j] + dp[i][j-1].
class Solution {
public:
int uniquePathsWithObstacles(vector<vector>>& grid) {
int filas = grid.size();
int cols = grid[0].size();
vector<vector>> dp(filas, vector<int>(cols, 0));
for (int r = 0; r < filas && !grid[r][0]; ++r) dp[r][0] = 1;
for (int c = 0; c < cols && !grid[0][c]; ++c) dp[0][c] = 1;
for (int i = 1; i < filas; ++i) {
for (int j = 1; j < cols; ++j) {
if (!grid[i][j]) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[filas - 1][cols - 1];
}
};</int></vector></vector>
6. División de entero
Enfoque: Sea dp[i] el producto máximo al dividir i. Para cada i, iterar j desde 0 hasta i-1: dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])). Inicialización: dp[0] = 0, dp[1] = 1.
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int val = 2; val <= n; ++val) {
for (int part = 0; part < val; ++part) {
dp[val] = max(dp[val], max(part * (val - part), part * dp[val - part]));
}
}
return dp[n];
}
};</int>
7. Árboles de búsqueda binaria distintos
Enfoque: Sea dp[i] el número de BST con nodos 1..i. Recurrencia: dp[i] += dp[j-1] * dp[i-j] para j de 1 a i. Inicialización: dp[0] = 1.
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
for (int nodes = 1; nodes <= n; ++nodes) {
for (int root = 1; root <= nodes; ++root) {
dp[nodes] += dp[root - 1] * dp[nodes - root];
}
}
return dp[n];
}
};</int>
Problemas de mochila
1. Mochila 0-1
Enfoque: Sea dp[i][c] el valor máximo usando los primeros i ítems con capacidad c. Recurrencia: dp[i][c] = max(dp[i-1][c], dp[i-1][c - peso[i]] + valor[i]). Inicialización en ceros. Optimización con arreglo unidimensional usando iteración inversa.
int knapsack01(int capacidad, vector<int>& peso, vector<int>& valor) {
int n = peso.size();
vector<int> dp(capacidad + 1, 0);
for (int i = 0; i < n; ++i) {
for (int c = capacidad; c >= peso[i]; --c) {
dp[c] = max(dp[c], dp[c - peso[i]] + valor[i]);
}
}
return dp[capacidad];
}</int></int></int>
2. Partición en subconjuntos iguales
Enfoque: Convertir a mochila 0-1 con objetivo sum/2. Sea dp[j] el máximo alcanzable con capacidad j. Recurrencia: dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]). Inicializcaión ceros, iteración inversa.
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size(), suma = 0;
for (int x : nums) suma += x;
if (suma % 2) return false;
vector<int> dp(10001, 0);
for (int i = 0; i < n; ++i) {
for (int j = suma / 2; j >= nums[i]; --j) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
if (dp[j] == suma / 2) return true;
}
}
return false;
}
};</int></int>
3. Último peso de piedras
Enfoque: Dividir piedras en dos montones para minimizar diferencia. Equivalente a mochila 0-1 con objetivo sum/2. Sea dp[j] el peso máximo en capacidad j. Recurrencia similar al anterior.
class Solution {
public:
int lastStoneWeightII(vector<int>& piedras) {
int n = piedras.size(), suma = 0;
for (int p : piedras) suma += p;
vector<int> dp(1501, 0);
for (int i = 0; i < n; ++i) {
for (int j = suma / 2; j >= piedras[i]; --j) {
dp[j] = max(dp[j], dp[j - piedras[i]] + piedras[i]);
}
}
return (suma - dp[suma / 2]) - dp[suma / 2];
}
};</int></int>
4. Suma objetivo
Enfoque: Convertir a mochila con capacidad pos = (sum + target)/2. Sea dp[j] el número de formas de alcanzar j. Recurrencia: dp[j] += dp[j - nums[i]]. Inicialización: dp[0] = 1.
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size(), suma = 0;
for (int x : nums) suma += x;
if ((suma + target) % 2 || abs(target) > suma) return 0;
int pos = (suma + target) / 2;
vector<int> dp(pos + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = pos; j >= nums[i]; --j) {
dp[j] += dp[j - nums[i]];
}
}
return dp[pos];
}
};</int></int>
5. Ceros y unos
Enfoque: Mochila con dos dimensiones: ceros y unos. Sea dp[a][b] el tamaño máximo del subconjunto con a ceros y b unos. Recurrencia: dp[a][b] = max(dp[a][b], dp[a - ceros][b - unos] + 1). Iteración inversa.
class Solution {
public:
int findMaxForm(vector<string>& strs, int maxCeros, int maxUnos) {
vector<vector>> dp(maxCeros + 1, vector<int>(maxUnos + 1, 0));
for (string s : strs) {
int ceros = count(s.begin(), s.end(), '0');
int unos = s.size() - ceros;
for (int a = maxCeros; a >= ceros; --a) {
for (int b = maxUnos; b >= unos; --b) {
dp[a][b] = max(dp[a][b], dp[a - ceros][b - unos] + 1);
}
}
}
return dp[maxCeros][maxUnos];
}
};</int></vector></string>
6. Mochila completa
Enfoque: Similar a 0-1 pero con ítems ilimitados. Optimización unidimensional con iteración ascendente. Recurrencia: dp[c] = max(dp[c], dp[c - peso[i]] + valor[i]).
int knapsackComplete(int capacidad, vector<int>& peso, vector<int>& valor) {
int n = peso.size();
vector<int> dp(capacidad + 1, 0);
for (int i = 0; i < n; ++i) {
for (int c = peso[i]; c <= capacidad; ++c) {
dp[c] = max(dp[c], dp[c - peso[i]] + valor[i]);
}
}
return dp[capacidad];
}</int></int></int>
7. Cambio de monedas II
Enfoque: Contar combinaciones (orden no importa). Sea dp[j] el número de combinaciones para monto j. Recurrencia: dp[j] += dp[j - monedas[i]]. Inicialización: dp[0] = 1. Iterar ítems primero, luego capacidad.
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = coins[i]; j <= amount; ++j) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};</int></int>
8. Suma total combinatoria IV
Enfoque: Contar permutaciones (orden importa). Sea dp[j] el número de permutaciones para objetivo j. Recurrencia: dp[j] += dp[j - nums[i]]. Inicialización: dp[0] = 1. Iterar capacidad primero, luego ítems.
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int n = nums.size();
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int j = 0; j <= target; ++j) {
for (int i = 0; i < n; ++i) {
if (nums[i] <= j && dp[j] < INT32_MAX - dp[j - nums[i]]) {
dp[j] += dp[j - nums[i]];
}
}
}
return dp[target];
}
};</int></int>
9. Escaleras con pasos variables
Enfoque: Contar permutaciones de pasos. Sea dp[j] el número de formas para escalón j. Recurrencia: dp[j] += dp[j - paso]. Inicialización: dp[0] = 1. Iterar capacidad primero.
int climbStairsVariante(int n, int maxPaso) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int j = 0; j <= n; ++j) {
for (int paso = 1; paso <= maxPaso; ++paso) {
if (j >= paso) dp[j] += dp[j - paso];
}
}
return dp[n];
}</int>
10. Cambio de monedas mínimo
Anfoque: Encontrar mínimo de monedas. Sea dp[j] el mínimo de monedas para monto j. Recurrencia: dp[j] = min(dp[j], dp[j - monedas[i]] + 1). Inicialización: dp[0] = 0, otros infinito.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> dp(amount + 1, 1e9);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = coins[i]; j <= amount; ++j) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == 1e9 ? -1 : dp[amount];
}
};</int></int>
11. Números cuadrados mínimos
Enfoque: Mínimo de cuadrados perfectos. Sea dp[j] el mínimo para j. Recurrencia: dp[j] = min(dp[j], dp[j - i*i] + 1). Inicialización: dp[0] = 0, otros infinito.
class Solution {
public:
int numSquares(int n) {
int m = sqrt(n);
vector<int> dp(n + 1, 1e9);
dp[0] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = i * i; j <= n; ++j) {
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};</int>
12. Segmentación de palabras
Enfoque: Determinar si una cadena puede segmentarse. Sea dp[j] verdadero si s[0..j-1] es segmentable. Recurrencia: si substring s[i..j-1] en diccionario y dp[i] verdadero, entonces dp[j] verdadero. Inicialización: dp[0] = true.
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int j = 1; j <= n; ++j) {
for (int i = 0; i < j; ++i) {
string sub = s.substr(i, j - i);
if (dict.find(sub) != dict.end() && dp[i]) {
dp[j] = true;
}
}
}
return dp[n];
}
};</bool></string></string>
13. Transporte de minerales
Enfoque: Mochila múltiple. Sea dp[j] el valor máximo con capacidad j. Recurrencia: para cada ítem con cantidad k, iterar k veces como 0-1. Iteración inversa.
int multipleKnapsack(int capacidad, vector<int>& peso, vector<int>& valor, vector<int>& cantidad) {
int n = peso.size();
vector<int> dp(capacidad + 1, 0);
for (int i = 0; i < n; ++i) {
for (int c = capacidad; c >= peso[i]; --c) {
for (int k = 1; k <= cantidad[i] && c >= k * peso[i]; ++k) {
dp[c] = max(dp[c], dp[c - k * peso[i]] + k * valor[i]);
}
}
}
return dp[capacidad];
}</int></int></int></int>
Problemas de robo en casas
1. Robo en casas
Enfoque: No robar casas adyacentes. Sea dp[i] el máximo robo hasta casa i. Recurrencia: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Inicialización: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
};</int></int>
2. Robo en casas circular
Enfoque: Casas en círculo, no robar primera y última juntas. Calcular dos casos: sin la primera casa y sin la última casa, luego tomar el máximo.
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
vector<int> dp1(n, 0), dp2(n, 0);
dp1[0] = nums[0];
dp1[1] = max(nums[0], nums[1]);
for (int i = 2; i < n - 1; ++i) {
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
dp2[n - 1] = nums[n - 1];
dp2[n - 2] = max(nums[n - 1], nums[n - 2]);
for (int i = n - 3; i > 0; --i) {
dp2[i] = max(dp2[i + 1], dp2[i + 2] + nums[i]);
}
return max(dp1[n - 2], dp2[1]);
}
};</int></int>
3. Robo en árbol binario
Enfoque: En cada nodo, decidir si robarlo o no. Usar DFS con vector de dos estados: con y sin robar el nodo actual. Recurrencia: si se roba, suma valor + sin robar hijos; si no, suma máximos de hijos.
class Solution {
public:
vector<int> dfs(TreeNode* node) {
if (!node) return {0, 0};
vector<int> izq = dfs(node->left);
vector<int> der = dfs(node->right);
int robar = node->val + izq[0] + der[0];
int noRobar = max(izq[0], izq[1]) + max(der[0], der[1]);
return {noRobar, robar};
}
int rob(TreeNode* root) {
vector<int> res = dfs(root);
return max(res[0], res[1]);
}
};</int></int></int></int>
Problemas de trading de acciones
1. Mejor momento para comprar y vender I
Enfoque: Una sola transacción. Sea dp[i][0] el beneficio si se tiene acción al día i, dp[i][1] si no. Recurrencia: dp[i][0] = max(dp[i-1][0], -precio[i]); dp[i][1] = max(dp[i-1][1], dp[i-1][0] + precio[i]). Inicialización: dp[0][0] = -precio[0], dp[0][1] = 0.
class Solution {
public:
int maxProfit(vector<int>& precios) {
int n = precios.size();
vector<vector>> dp(n, vector<int>(2, 0));
dp[0][0] = -precios[0];
dp[0][1] = 0;
for (int dia = 1; dia < n; ++dia) {
dp[dia][0] = max(dp[dia - 1][0], -precios[dia]);
dp[dia][1] = max(dp[dia - 1][1], dp[dia - 1][0] + precios[dia]);
}
return dp[n - 1][1];
}
};</int></vector></int>
2. Mejor momento II
Enfoque: Múltiples transacciones. Recurrencia similar, pero al comprar considerar beneficios anteriores: dp[i][0] = max(dp[i-1][0], dp[i-1][1] - precio[i]).
class Solution {
public:
int maxProfit(vector<int>& precios) {
int n = precios.size();
vector<vector>> dp(n, vector<int>(2, 0));
dp[0][0] = -precios[0];
dp[0][1] = 0;
for (int dia = 1; dia < n; ++dia) {
dp[dia][0] = max(dp[dia - 1][0], dp[dia - 1][1] - precios[dia]);
dp[dia][1] = max(dp[dia - 1][1], dp[dia - 1][0] + precios[dia]);
}
return dp[n - 1][1];
}
};</int></vector></int>
3. Mejor momento III
Enfoque: Hasta dos transacciones. Estados: no operar, primera compra, primera venta, segunda compra, segunda venta. Recurrencia análoga.
class Solution {
public:
int maxProfit(vector<int>& precios) {
int n = precios.size();
vector<vector>> dp(n, vector<int>(5, 0));
dp[0][1] = -precios[0];
dp[0][3] = -precios[0];
for (int dia = 1; dia < n; ++dia) {
dp[dia][1] = max(dp[dia - 1][1], dp[dia - 1][0] - precios[dia]);
dp[dia][2] = max(dp[dia - 1][2], dp[dia - 1][1] + precios[dia]);
dp[dia][3] = max(dp[dia - 1][3], dp[dia - 1][2] - precios[dia]);
dp[dia][4] = max(dp[dia - 1][4], dp[dia - 1][3] + precios[dia]);
}
return dp[n - 1][4];
}
};</int></vector></int>
4. Mejor momento IV
Enfoque: Generalizar para k transacciones. Estados pares: ventas, impares: compras. Inicializar compras en -precio[0]. Recurrancia: para cada transacción par/impar.
class Solution {
public:
int maxProfit(int k, vector<int>& precios) {
int n = precios.size();
vector<vector>> dp(n, vector<int>(2 * k + 1, 0));
for (int i = 1; i < 2 * k; i += 2) dp[0][i] = -precios[0];
for (int dia = 1; dia < n; ++dia) {
for (int trans = 1; trans < 2 * k; trans += 2) {
dp[dia][trans] = max(dp[dia - 1][trans], dp[dia - 1][trans - 1] - precios[dia]);
dp[dia][trans + 1] = max(dp[dia - 1][trans + 1], dp[dia - 1][trans] + precios[dia]);
}
}
return dp[n - 1][2 * k];
}
};</int></vector></int>
5. Con período de enfriamiento
Enfoque: Estados: tener acción, no tener acción, vender hoy, enfriamiento. Recurrencia: dp[i][0] = max(dp[i-1][0], dp[i-1][3] - precio[i], dp[i-1][1] - precio[i]), etc.
class Solution {
public:
int maxProfit(vector<int>& precios) {
int n = precios.size();
vector<vector>> dp(n, vector<int>(4, 0));
dp[0][0] = -precios[0];
for (int dia = 1; dia < n; ++dia) {
dp[dia][0] = max(dp[dia - 1][0], max(dp[dia - 1][3] - precios[dia], dp[dia - 1][1] - precios[dia]));
dp[dia][1] = max(dp[dia - 1][1], dp[dia - 1][3]);
dp[dia][2] = dp[dia - 1][0] + precios[dia];
dp[dia][3] = dp[dia - 1][2];
}
return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][3]));
}
};</int></vector></int>
6. Con comisión
Enfoque: Similar, con comisión al comprar o vender. Ajustar recurrencia: al comprar restar comisión, o al vender restar comisión.
class Solution {
public:
int maxProfit(vector<int>& precios, int fee) {
int n = precios.size();
vector<vector>> dp(n, vector<int>(2, 0));
dp[0][0] = -precios[0] - fee;
for (int dia = 1; dia < n; ++dia) {
dp[dia][0] = max(dp[dia - 1][0], dp[dia - 1][1] - precios[dia] - fee);
dp[dia][1] = max(dp[dia - 1][1], dp[dia - 1][0] + precios[dia]);
}
return dp[n - 1][1];
}
};</int></vector></int>
Problemas de subsecuencias
1. Subsecuencia creciente más larga
Enfoque: Sea dp[i] la longitud de la subsecuencia más larga terminando en i. Recurrencia: para j < i, si nums[i] > nums[j], dp[i] = max(dp[i], dp[j] + 1). Inicialización: dp[i] = 1.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int maximo = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maximo = max(maximo, dp[i]);
}
return maximo;
}
};</int></int>
2. Subsecuencia creciente continua más larga
Enfoque: Subsecuencia contigua. Sea dp[i] la longitud máxima terminando en i. Recurrencia: si nums[i] > nums[i-1], dp[i] = dp[i-1] + 1.
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int maximo = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
}
maximo = max(maximo, dp[i]);
}
return maximo;
}
};</int></int>
3. Subarreglo repetido más largo
Enfoque: Dos arrays. Sea dp[i][j] la longitud del subarreglo común terminando en i-1 y j-1. Recurrencia: si nums1[i-1] == nums2[j-1], dp[i][j] = dp[i-1][j-1] + 1.
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int n = A.size(), m = B.size();
vector<vector>> dp(n + 1, vector<int>(m + 1, 0));
int res = 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;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};</int></vector></int></int>
4. Subsecuencia común más larga
Enfoque: Similar, pero subsecuencia no contigua. Si caracteres iguales, dp[i][j] = dp[i-1][j-1] + 1; si no, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size();
vector<vector>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (text1[i - 1] == text2[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];
}
};</int></vector>
5. Líneas no cruzadas
Enfoque: Equivalente a subsecuencia común más larga.
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
vector<vector>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (nums1[i - 1] == nums2[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];
}
};</int></vector></int></int>
6. Suma máxima de subarreglo
Enfoque: Sea dp[i] la suma máxima terminando en i. Recurrencia: dp[i] = max(dp[i-1] + nums[i], nums[i]).
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int maximo = nums[0];
for (int i = 1; i < n; ++i) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
maximo = max(maximo, dp[i]);
}
return maximo;
}
};</int></int>
7. Verificar subsecuencia
Enfoque: Usar LCS o DP simple. Sea dp[i][j] la longitud de subsecuencia común. Si s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] + 1; si no, dp[i][j] = dp[i][j-1]. Finalmente, verificar si dp[n][m] == n.
class Solution {
public:
bool isSubsequence(string s, string t) {
int n = s.size(), m = t.size();
vector<vector>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[n][m] == n;
}
};</int></vector>
8. Subsecuencias distintas
Enfoque: Contar subsecuencias de s que forman t. Sea dp[i][j] el número de formas. Si t[i-1] == s[j-1], dp[i][j] = dp[i-1][j-1] + dp[i][j-1]; si no, dp[i][j] = dp[i][j-1]. Inicialización: dp[0][j] = 1.
class Solution {
public:
int numDistinct(string s, string t) {
int n = t.size(), m = s.size();
vector<vector>> dp(n + 1, vector<int>(m + 1, 0));
for (int j = 0; j <= m; ++j) dp[0][j] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (t[i - 1] == s[j - 1]) {
dp[i][j] = (dp[i - 1][j - 1] + dp[i][j - 1]) % 1000000007;
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[n][m];
}
};</int></vector>
9. Operaciones de eliminación para igualar strings
Enfoque: Encontrar mínimo de eliminaciones. Sea dp[i][j] el mínimo para igualar word1[0..i-1] y word2[0..j-1]. Si iguales, dp[i][j] = dp[i-1][j-1]; si no, dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1. Inicialización: dp[i][0] = i, dp[0][j] = j.
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
vector<vector>> 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 (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[n][m];
}
};</int></vector>
10. Distancia de edición
Enfoque: Insertar, eliminar, reemplazar. Sea dp[i][j] el mínimo de operaciones. Si iguales, dp[i][j] = dp[i-1][j-1]; si no, dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1.
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
vector<vector>> 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 (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
return dp[n][m];
}
};</int></vector>
11. Substrings palindrómicos
Enfoque: Sea dp[i][j] verdadero si s[i..j] es palíndromo. Recurrencia: si s[i] == s[j] y (j-i<=1 o dp[i+1][j-1]), entonces dp[i][j] verdadero. Iterar desde el final hacia el inicio.
class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector>> dp(n, vector<bool>(n, false));
int conteo = 0;
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
dp[i][j] = true;
++conteo;
}
}
}
return conteo;
}
};</bool></vector>
12. Subsecuencia palindrómica más larga
Enfoque: Sea dp[i][j] la longitud máxima de palíndromo en s[i..j]. Si s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; si no, dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Inicialización: dp[i][i] = 1.
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
};</int></vector>