Problema: Calcular el número de formas de alcanzar sumas específicas usando un conjunto de items, y luego determinar el efecto de remover cada item individualmente.

Solución: Se utiliza DP para calcular todas las combinaciones y luego se sustrae la contribución de cada item usando recálculo parcial.

// Código modificado para el problema P4141
#include <iostream>
#include <vector>
using namespace std;

const int LIMITE_PESO = 4020;

int main() {
    int num_items, capacidad;
    cin >> num_items >> capacidad;
    vector<int> pesos(num_items);
    for (int i = 0; i < num_items; ++i) cin >> pesos[i];
    
    vector<int> dp_total(capacidad + 1, 0);
    dp_total[0] = 1;
    // Calcular DP considerando todos los items
    for (int k = 0; k < num_items; ++k) {
        for (int j = capacidad; j >= pesos[k]; --j) {
            dp_total[j] = (dp_total[j] + dp_total[j - pesos[k]]) % 10;
        }
    }
    
    vector<vector<int>> resultados(num_items, vector<int>(capacidad + 1));
    for (int i = 0; i < num_items; ++i) {
        vector<int> dp_excluido(capacidad + 1, 0);
        dp_excluido[0] = 1;
        // Recalcular DP excluyendo el item actual
        for (int k = 0; k < num_items; ++k) {
            if (k == i) continue;
            for (int j = capacidad; j >= pesos[k]; --j) {
                dp_excluido[j] = (dp_excluido[j] + dp_excluido[j - pesos[k]]) % 10;
            }
        }
        for (int j = 1; j <= capacidad; ++j) {
            resultados[i][j] = (dp_total[j] - dp_excluido[j] + 10) % 10;
        }
    }
    
    for (int i = 0; i < num_items; ++i) {
        for (int j = 1; j <= capacidad; ++j) {
            cout << resultados[i][j];
        }
        cout << endl;
    }
    return 0;
}

Ejemplo 2: DP de Intervalos para Minimización

Problema: Dado un arreglo, encontrar el costo mínimo para reducirlo a un solo elemento mediante operaciones de combinación.

Solución: Se aplica DP de intervalos, donde dp[i][j] representa el costo mínimo para el subarreglo de i a j.

// Código modificado para el problema CF607B
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int longitud;
    cin >> longitud;
    vector<int> elementos(longitud + 1);
    for (int i = 1; i <= longitud; ++i) cin >> elementos[i];
    
    vector<vector<int>> dp(longitud + 2, vector<int>(longitud + 2, 1e9));
    for (int i = 1; i <= longitud; ++i) dp[i][i] = 1;
    for (int len = 2; len <= longitud; ++len) {
        for (int izq = 1; izq <= longitud - len + 1; ++izq) {
            int der = izq + len - 1;
            if (len == 2) {
                dp[izq][der] = (elementos[izq] == elementos[der]) ? 1 : 2;
                continue;
            }
            for (int k = izq; k < der; ++k) {
                dp[izq][der] = min(dp[izq][der], dp[izq][k] + dp[k + 1][der]);
            }
            if (elementos[izq] == elementos[der]) {
                dp[izq][der] = min(dp[izq][der], dp[izq + 1][der - 1]);
            }
        }
    }
    cout << dp[1][longitud];
    return 0;
}

Ejemplo 3: DP de Dígitos con Transformaciones

Problema: Para una cadena numérica, calcular la longitud total después de múltiples transformaciones donde cada dígito se convierte en dos.

Solución: Precomputar la longitud resultante para cada dígito y número de transformaciones usando DP.

// Código modificado para el problema CF1513C
#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MODULO = 1e9 + 7;
const int MAX_TRANSFORMACIONES = 3e5 + 10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // Precomputar longitudes: dp[t][d] = longitud del dígito d después de t transformaciones
    vector<vector<int>> longitudes(MAX_TRANSFORMACIONES, vector<int>(10));
    for (int d = 0; d <= 9; ++d) longitudes[0][d] = 1;
    for (int t = 1; t < MAX_TRANSFORMACIONES; ++t) {
        for (int d = 0; d <= 8; ++d) {
            longitudes[t][d] = longitudes[t - 1][d + 1];
        }
        longitudes[t][9] = (longitudes[t - 1][1] + longitudes[t - 1][0]) % MODULO;
    }
    
    int casos_prueba;
    cin >> casos_prueba;
    while (casos_prueba--) {
        string cadena;
        int transformaciones;
        cin >> cadena >> transformaciones;
        int suma = 0;
        for (char c : cadena) {
            suma = (suma + longitudes[transformaciones][c - '0']) % MODULO;
        }
        cout << suma << endl;
    }
    return 0;
}

Ejemplo 4: DP con Estados Múltiples para Árboles y Colores

Problema: Colorear árboles con restricciones de grupos, minimizando el costo total.

Solución: DP con tres dimensiones: posición, color actual y número de grupos usados.

// Código modificado para el problema CF711C
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
    int num_arboles, num_colores, grupos_max;
    cin >> num_arboles >> num_colores >> grupos_max;
    vector<int> colores_predefinidos(num_arboles + 1);
    for (int i = 1; i <= num_arboles; ++i) cin >> colores_predefinidos[i];
    vector<vector<int>> costos(num_arboles + 1, vector<int>(num_colores + 1));
    for (int i = 1; i <= num_arboles; ++i) {
        for (int j = 1; j <= num_colores; ++j) {
            cin >> costos[i][j];
        }
    }
    
    // dp[pos][color][grupos] = costo mínimo
    vector<vector<vector<int>>> dp(num_arboles + 1, vector<vector<int>>(num_colores + 1, vector<int>(grupos_max + 1, 1e18)));
    if (colores_predefinidos[1] != 0) {
        dp[1][colores_predefinidos[1]][1] = 0;
    } else {
        for (int c = 1; c <= num_colores; ++c) {
            dp[1][c][1] = costos[1][c];
        }
    }
    for (int i = 2; i <= num_arboles; ++i) {
        if (colores_predefinidos[i] != 0) {
            int color_actual = colores_predefinidos[i];
            for (int color_ant = 1; color_ant <= num_colores; ++color_ant) {
                for (int g = 1; g <= grupos_max; ++g) {
                    if (color_ant != color_actual) {
                        dp[i][color_actual][g] = min(dp[i][color_actual][g], dp[i - 1][color_ant][g - 1]);
                    } else {
                        dp[i][color_actual][g] = min(dp[i][color_actual][g], dp[i - 1][color_actual][g]);
                    }
                }
            }
        } else {
            for (int color_actual = 1; color_actual <= num_colores; ++color_actual) {
                for (int color_ant = 1; color_ant <= num_colores; ++color_ant) {
                    for (int g = 1; g <= grupos_max; ++g) {
                        int costo_adicional = (color_ant != color_actual) ? costos[i][color_actual] : 0;
                        if (color_ant != color_actual) {
                            dp[i][color_actual][g] = min(dp[i][color_actual][g], dp[i - 1][color_ant][g - 1] + costo_adicional);
                        } else {
                            dp[i][color_actual][g] = min(dp[i][color_actual][g], dp[i - 1][color_actual][g] + costo_adicional);
                        }
                    }
                }
            }
        }
    }
    
    int resultado = 1e18;
    if (colores_predefinidos[num_arboles] != 0) {
        resultado = dp[num_arboles][colores_predefinidos[num_arboles]][grupos_max];
    } else {
        for (int c = 1; c <= num_colores; ++c) {
            resultado = min(resultado, dp[num_arboles][c][grupos_max]);
        }
    }
    cout << (resultado >= 1e18 ? -1 : resultado);
    return 0;
}

Ejemplo 5: DP para Cadenas con Inversiones

Problema: Dado una secuencia de cadenas, decidir cuándo invertirlas para mantener el orden no decreciente, minimizando el costo.

Solución: DP con dos estados por posición: cadena original o invertida.

// Código modificado para el problema CF706C
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> costos(n + 1);
    for (int i = 1; i <= n; ++i) cin >> costos[i];
    vector<string> cadenas(n + 1), invertidas(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> cadenas[i];
        invertidas[i] = cadenas[i];
        reverse(invertidas[i].begin(), invertidas[i].end());
    }
    
    // dp[i][0] = costo mínimo hasta i usando cadena original
    // dp[i][1] = costo mínimo hasta i usando cadena invertida
    vector<vector<long long>> dp(n + 1, vector<long long>(2, 1e18));
    dp[1][0] = 0;
    dp[1][1] = costos[1];
    for (int i = 2; i <= n; ++i) {
        if (cadenas[i] >= cadenas[i - 1]) dp[i][0] = min(dp[i][0], dp[i - 1][0]);
        if (invertidas[i] >= invertidas[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][1] + costos[i]);
        if (invertidas[i] >= cadenas[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][0] + costos[i]);
        if (cadenas[i] >= invertidas[i - 1]) dp[i][0] = min(dp[i][0], dp[i - 1][1]);
    }
    long long min_costo = min(dp[n][0], dp[n][1]);
    cout << (min_costo >= 1e18 ? -1 : min_costo);
    return 0;
}

Ejemplo 6: DP para Distancia de Edición

Problema: Encontrar el número mínimo de operaciones (inserción, eliminación, sustitución) para transformar una cadena en otra.

Solución: DP clásico donde dp[i][j] es el costo para trensformar los primeros i caracteres en los primeros j.

// Código modificado para el problema P2758
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string origen, destino;
    cin >> origen >> destino;
    int len_origen = origen.size(), len_destino = destino.size();
    vector<vector<int>> dp(len_origen + 1, vector<int>(len_destino + 1));
    for (int i = 0; i <= len_origen; ++i) dp[i][0] = i;
    for (int j = 0; j <= len_destino; ++j) dp[0][j] = j;
    
    for (int i = 1; i <= len_origen; ++i) {
        for (int j = 1; j <= len_destino; ++j) {
            int costo_sustitucion = (origen[i - 1] == destino[j - 1]) ? 0 : 1;
            dp[i][j] = min({
                dp[i - 1][j] + 1,        // Eliminación
                dp[i][j - 1] + 1,        // Inserción
                dp[i - 1][j - 1] + costo_sustitucion  // Sustitución
            });
        }
    }
    cout << dp[len_origen][len_destino];
    return 0;
}

Ejemplo 7: DP con Diferencias Aritméticas

Problema: Contar el número de subsecuencias con diferencias constantes.

Solución: DP con estados que almacenan el último valor y la diferencia común.

// Código modificado para el problema P4933
#include <iostream>
#include <vector>
using namespace std;

const int MODULO = 998244353;
const int DESPLAZAMIENTO = 20000;

int main() {
    int n;
    cin >> n;
    vector<int> valores(n + 1);
    for (int i = 1; i <= n; ++i) cin >> valores[i];
    
    // dp[i][d] = número de subsecuencias terminando en i con diferencia d
    vector<vector<int>> dp(n + 1, vector<int>(2 * DESPLAZAMIENTO + 1, 0));
    long long total = 0;
    for (int i = 1; i <= n; ++i) {
        total = (total + 1) % MODULO; // Subsecuencia de un solo elemento
        for (int j = 1; j < i; ++j) {
            int diff = valores[i] - valores[j] + DESPLAZAMIENTO;
            dp[i][diff] = (dp[i][diff] + dp[j][diff] + 1) % MODULO;
            total = (total + dp[j][diff] + 1) % MODULO;
        }
    }
    cout << total % MODULO;
    return 0;
}

Ejemplo 8: DP en Árboles para Bloques Conectados

Problema: Encontrar la suma máxima de un bloque conectado en un árbol.

Solución: DP donde cada nodo calcula la mejor suma considerando sus hijos.

// Código modificado para el problema P8625
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> grafo;
vector<long long> valores, dp;

void dfs(int nodo, int padre) {
    dp[nodo] = valores[nodo];
    for (int hijo : grafo[nodo]) {
        if (hijo != padre) {
            dfs(hijo, nodo);
            dp[nodo] = max(dp[nodo], dp[nodo] + dp[hijo]);
        }
    }
}

int main() {
    int num_nodos;
    cin >> num_nodos;
    grafo.resize(num_nodos + 1);
    valores.resize(num_nodos + 1);
    dp.resize(num_nodos + 1, 0);
    for (int i = 1; i <= num_nodos; ++i) cin >> valores[i];
    for (int i = 0; i < num_nodos - 1; ++i) {
        int u, v;
        cin >> u >> v;
        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }
    dfs(1, 0);
    long long max_suma = *max_element(dp.begin() + 1, dp.end());
    cout << max_suma;
    return 0;
}

Ejemplo 9: DP Matricial para Submatrices Cuadradas

Problema: Contar submatrices cuadradas llenas de unos en una matriz binaria.

Solución: Usar DP para calcular el tamaño máximo de submatrices cuadradas en cada posición.

// Código modificado para el problema P2733
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matriz(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            char c;
            cin >> c;
            matriz[i][j] = c - '0';
        }
    }
    
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    vector<int> conteos(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (matriz[i][j] == 1) {
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                for (int k = 2; k <= dp[i][j]; ++k) {
                    conteos[k]++;
                }
            }
        }
    }
    
    for (int k = 2; k <= n; ++k) {
        if (conteos[k] > 0) {
            cout << k << ' ' << conteos[k] << endl;
        }
    }
    return 0;
}

Ejemplo 10: DP Multidimensional para Múltiples Recorridos

Problema: Encontrar la suma máxima recorriendo una matriz dos veces desde la esquina superier izquierda a la inferior derecha.

Solución: DP con cuatro dimensiones para representar las posiciones de ambos recorridos simultáneamente.

// Código modificado para el problema P1004
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grilla(n + 1, vector<int>(n + 1, 0));
    int r, c, valor;
    while (cin >> r >> c >> valor && r + c + valor > 0) {
        grilla[r][c] = valor;
    }
    
    // dp[i][j][k][l] = suma máxima para recorridos hasta (i,j) y (k,l)
    vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0))));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                for (int l = 1; l <= n; ++l) {
                    dp[i][j][k][l] = max({
                        dp[i - 1][j][k - 1][l],
                        dp[i - 1][j][k][l - 1],
                        dp[i][j - 1][k - 1][l],
                        dp[i][j - 1][k][l - 1]
                    }) + grilla[i][j] + grilla[k][l];
                    if (i == k && j == l) dp[i][j][k][l] -= grilla[k][l];
                }
            }
        }
    }
    cout << dp[n][n][n][n];
    return 0;
}

Estos ejercicios ilustran diversas aplicaciones de la programación dinámica, desde problemas básicos hasta técnicas avanzadas. La práctica constante con diferentes tipos de problemas ayuda a desarrollar habilidades sólidas en resolución de algoritmos.