Ruta Mínima en Triángulo

Dado un triángulo de números positivos, encuentra la suma mínima de la ruta desde la cima hasta la base. Solo puedes moverte a nodos adyacentes en la siguiente fila.

#include <vector>
#include <algorithm>
using namespace std;

int rutaMinima(vector<vector<int>>& triangulo) {
    int niveles = triangulo.size();
    for (int i = niveles - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            triangulo[i][j] += min(triangulo[i+1][j], triangulo[i+1][j+1]);
        }
    }
    return triangulo[0][0];
}

Maximización de Robo en Hogares

Calcula la cantidad máxima que puedes robar de casas alineadas sin saquear dos casas adyacentes.

#include <vector>
#include <algorithm>
using namespace std;

int roboMaximo(vector<int>& valores) {
    int n = valores.size();
    if (n == 0) return 0;
    vector<int> dp(n, 0);
    dp[0] = valores[0];
    if (n > 1) dp[1] = max(valores[0], valores[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + valores[i]);
    }
    return dp[n-1];
}

Segmentación de Palabras

Determina si una cadena puede dividirse en palabras existentes en un diccionario dado.

#include <vector>
#include <unordered_set>
using namespace std;

bool segmentarCadena(string s, vector<string>& diccionario) {
    unordered_set<string> palabras(diccionario.begin(), diccionario.end());
    vector<bool> valido(s.size()+1, false);
    valido[0] = true;
    for (int fin = 1; fin <= s.size(); fin++) {
        for (int ini = 0; ini < fin; ini++) {
            string segmento = s.substr(ini, fin - ini);
            if (valido[ini] && palabras.find(segmento) != palabras.end()) {
                valido[fin] = true;
                break;
            }
        }
    }
    return valido[s.size()];
}

Cambio de Monedas

Calcula el número mínimo de monedas necesarias para obtener una cantidad específica.

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int cambioMinimo(vector<int>& monedas, int cantidad) {
    vector<int> dp(cantidad + 1, cantidad + 1);
    dp[0] = 0;
    for (int i = 1; i <= cantidad; i++) {
        for (int mon : monedas) {
            if (i >= mon) {
                dp[i] = min(dp[i], dp[i - mon] + 1);
            }
        }
    }
    return (dp[cantidad] > cantidad) ? -1 : dp[cantidad];
}

Subsecuencia Creciente Máxima

Encuentra la longitud de la subsecuencia estrictamente creciente más larga en una secuencia numérica.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> secuencia(n);
    vector<int> dp(n, 1);
    int maxLongitud = 0;
    for (int i = 0; i < n; i++) {
        cin >> secuencia[i];
        for (int j = 0; j < i; j++) {
            if (secuencia[j] < secuencia[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLongitud = max(maxLongitud, dp[i]);
    }
    cout << maxLongitud;
}

Subsecuencia Común Máxima

Calcula la longitud de la subsecuencia común más larga entre dos cadanas.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    string cadA, cadB;
    cin >> cadA >> cadB;
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (cadA[i-1] == cadB[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << dp[m][n];
}

Optimización de Espacio en Contenedor

Minimiza el espacio no utilizado en un contenedor seleccionando objetos adecuados.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int capacidad, numObjetos;
    cin >> capacidad >> numObjetos;
    vector<int> objetos(numObjetos);
    vector<bool> dp(capacidad + 1, false);
    dp[0] = true;
    for (int obj : objetos) {
        cin >> obj;
        for (int vol = capacidad; vol >= obj; vol--) {
            if (dp[vol - obj]) dp[vol] = true;
        }
    }
    int usado = capacidad;
    while (!dp[usado]) usado--;
    cout << capacidad - usado;
}

Problema de la Mochila 0/1

Selecciona objetos para maximizar el valor sin exceder la capacidad de la mochila.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int numObjetos, capacidad;
    cin >> numObjetos >> capacidad;
    vector<int> volumenes(numObjetos), valores(numObjetos);
    vector<vector<int>> dp(numObjetos + 1, vector<int>(capacidad + 1, INT_MIN));
    dp[0][0] = 0;
    for (int i = 1; i <= numObjetos; i++) {
        cin >> volumenes[i-1] >> valores[i-1];
        for (int cap = 0; cap <= capacidad; cap++) {
            dp[i][cap] = dp[i-1][cap];
            if (cap >= volumenes[i-1] && dp[i-1][cap - volumenes[i-1]] != INT_MIN) {
                dp[i][cap] = max(dp[i][cap], dp[i-1][cap - volumenes[i-1]] + valores[i-1]);
            }
        }
    }
    int maxValor = 0;
    for (int cap = 0; cap <= capacidad; cap++) {
        maxValor = max(maxValor, dp[numObjetos][cap]);
    }
    int exacto = (dp[numObjetos][capacidad] < 0) ? 0 : dp[numObjetos][capacidad];
    cout << maxValor << endl << exacto;
}

Gestión de Presupuesto para Compras

Optimiza compras considerando productos principales y accesorios con un presupuesto limitado.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int presupuesto, numProductos;
    cin >> presupuesto >> numProductos;
    presupuesto /= 10;
    vector<vector<int>> precios(61, vector<int>(3, 0));
    vector<vector<int>> valores(61, vector<int>(3, 0));
    vector<vector<int>> dp(numProductos + 1, vector<int>(presupuesto + 1, 0));
    for (int id = 1; id <= numProductos; id++) {
        int precio, prioridad, tipo;
        cin >> precio >> prioridad >> tipo;
        precio /= 10;
        if (tipo == 0) {
            precios[id][0] = precio;
            valores[id][0] = precio * prioridad;
        } else {
            if (precios[tipo][1] == 0) {
                precios[tipo][1] = precio;
                valores[tipo][1] = precio * prioridad;
            } else {
                precios[tipo][2] = precio;
                valores[tipo][2] = precio * prioridad;
            }
        }
    }
    for (int id = 1; id <= numProductos; id++) {
        for (int pres = 1; pres <= presupuesto; pres++) {
            dp[id][pres] = dp[id-1][pres];
            int p0 = precios[id][0], v0 = valores[id][0];
            int p1 = precios[id][1], v1 = valores[id][1];
            int p2 = precios[id][2], v2 = valores[id][2];
            if (p0 > 0 && pres >= p0) {
                dp[id][pres] = max(dp[id][pres], dp[id-1][pres - p0] + v0);
            }
            if (p1 > 0 && pres >= p0 + p1) {
                dp[id][pres] = max(dp[id][pres], dp[id-1][pres - p0 - p1] + v0 + v1);
            }
            if (p2 > 0 && pres >= p0 + p2) {
                dp[id][pres] = max(dp[id][pres], dp[id-1][pres - p0 - p2] + v0 + v2);
            }
            if (p1 > 0 && p2 > 0 && pres >= p0 + p1 + p2) {
                dp[id][pres] = max(dp[id][pres], dp[id-1][pres - p0 - p1 - p2] + v0 + v1 + v2);
            }
        }
    }
    cout << dp[numProductos][presupuesto] * 10;
}

Ruta Mínima en Matriz

Encuentra la ruta de suma mínima desde la esquina superior izquierda hasta la inferior derecha en una matriz.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int filas, columnas;
    cin >> filas >> columnas;
    vector<vector<int>> matriz(filas, vector<int>(columnas));
    vector<vector<int>> dp(filas, vector<int>(columnas, 0));
    for (int i = 0; i < filas; i++) {
        for (int j = 0; j < columnas; j++) {
            cin >> matriz[i][j];
        }
    }
    dp[0][0] = matriz[0][0];
    for (int j = 1; j < columnas; j++) dp[0][j] = dp[0][j-1] + matriz[0][j];
    for (int i = 1; i < filas; i++) dp[i][0] = dp[i-1][0] + matriz[i][0];
    for (int i = 1; i < filas; i++) {
        for (int j = 1; j < columnas; j++) {
            dp[i][j] = matriz[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[filas-1][columnas-1];
}

Subsecuencia Palindrómica Máxima

Calcula la longitud de la subsecuencia palindrómica más larga en una cadena.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string texto;
    cin >> texto;
    int n = texto.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int longSeg = 2; longSeg <= n; longSeg++) {
        for (int ini = 0; ini <= n - longSeg; ini++) {
            int fin = ini + longSeg - 1;
            if (texto[ini] == texto[fin]) {
                dp[ini][fin] = dp[ini+1][fin-1] + 2;
            } else {
                dp[ini][fin] = max(dp[ini+1][fin], dp[ini][fin-1]);
            }
        }
    }
    cout << dp[0][n-1];
}

Salto Mínimo en Juego

Calcula el número mínimo de saltos necesarios para alcanzar el final de un arreglo.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> saltos(n);
    vector<int> dp(n, INT_MAX);
    for (int i = 0; i < n; i++) cin >> saltos[i];
    dp[0] = 0;
    for (int pos = 0; pos < n; pos++) {
        int alcance = min(n - 1, pos + saltos[pos]);
        for (int sig = pos + 1; sig <= alcance; sig++) {
            dp[sig] = min(dp[sig], dp[pos] + 1);
        }
    }
    cout << (dp[n-1] == INT_MAX ? -1 : dp[n-1]);
}