- Problemas del Día
Problema de Mochila con Repetición (Séptimo Examen de Simulación)
Problema de Cambio de Monedas II (LeetCode 518)
Problema de Suma de Combinaciones IV (LeetCode 377)
Problema de Escaleras Avanzado (Octavo Examen de Simulación)
- Cinco Pasos de la Programación Dinámica
Significado de la matriz dp y sus índices
Inicialización de la matriz dp
Ecuación de transición de estados
Orden de recorrido
Simulación manual
- Problema de Mochila con Repetición
3.1 Enfoque
Paso 1:
Significado de dp[i][j] y sus índices dp[i][j] representa: considerando los primeros i+1 objetos (del 0 al i), con una capacidad de mochila de j, el valor máximo que se puede incluir (los objetos se pueden seleccionar infinitamente); Índice i: corresponde al índice del objeto (0n-1), indica "cuántos objetos se han procesado"; Índice j: corresponde a la capacidad de la mochila (0capacidadMochila), indica "capacidad actual de la mochila"; Diferencia clave (con respecto a la mochila 0-1): al seleccionar el objeto i en dp[i][j], se puede reutilizar dp[i][j-peso[i]] (resultado de haber seleccionado ese objeto ya en la fila actual).
Paso 2:
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-peso[i]] + valor[i]); Explicado en términos simples: dp[i-1][j]: no seleccionar el objeto actual i → el resultado hereda el valor máximo de "los primeros i objetos (0~i-1) con capacidad j" (igual que en mochila 0-1); dp[i][j-peso[i]] + valor[i]: seleccionar el objeto actual i → como los objetos se pueden seleccionar infinitamente, después de seleccionar uno, se puede seleccionar nuevamente, por lo que se usa el resultado de "fila actual i con capacidad j-peso[i]" (en lugar de la fila anterior i-1), más el valor del objeto actual; max: elegir el de mayor valor entre "seleccionar" y "no seleccionar" (igual que en mochila 0-1, buscando el valor óptimo).
Paso 3:
Cuando la capacidad es 0 (j=0): dp[i][0] = 0 → con capacidad de mochila 0, no se puede incluir ningún objeto, el valor es 0; Solo con el primer objeto (i=0): como los objetos se pueden seleccionar infinitamente, cuando j >= peso[0], el valor es "número máximo que se puede incluir × valor[0]", es decir: dp[0][j] = dp[0][j - peso[0]] + valor[0]; Por ejemplo, objeto 0 con peso 2 y valor 3, capacidad 6: dp[0][6] = dp[0][4]+3 = dp[0][2]+3+3 = dp[0][0]+3+3+3 = 9 (se incluyen 3 objetos, cumple con la regla de selección infinita); El valor predeterminado de la matriz es 0, no es necesario asignar cuando j < peso[0] (el valor es 0).
Paso 4:
Bucle externo (objetos): i de 1 a n-1 → recorrer en orden de objetos, ya que dp[i][j] depende de dp[i-1][j] (no seleccionar objeto actual) y dp[i][j-peso[i]] (seleccionar objeto actual); Bucle interno (capacidad): j de 0 a capacidadMochila → recorrer en orden normal (igual que la versión bidimensional de mochila 0-1, sin necesidad de orden inverso).
Paso 5:
Caso de prueba: n=2, capacidadMochila=5; peso = [1, 3], valor = [2, 4]; Objeto 0: peso 1, valor 2 (se puede seleccioanr infinitamente); objeto 1: peso 3, valor 4 (se puede seleccionar infinitamente). Paso 1: Inicialización Capacidad 0: dp[i][0] = 0 (todas las filas, columna 0 son 0); Primer objeto (i=0): j=1: dp[0][1] = dp[0][0]+2 = 2; j=2: dp[0][2] = dp[0][1]+2 = 4; j=3: dp[0][3] = 6; j=4: 8; j=5: 10; → dp[0] = [0,2,4,6,8,10]. Paso 2: Recorrer segundo objeto (i=1, peso=3, valor=4) Calcular cada capacidad j: j=0: dp[1][0] = 0; j=1: j < 3 → dp[1][1] = dp[0][1] = 2; j=2: j < 3 → dp[1][2] = dp[0][2] = 4; j=3: j ≥3 → max(dp[0][3]=6, dp[1][0]+4=4) → 6; j=4: j ≥3 → max(dp[0][4]=8, dp[1][1]+4=6) → 8; j=5: j ≥3 → max(dp[0][5]=10, dp[1][2]+4=8) → 10; → dp[1] = [0,2,4,6,8,10]; Resultado final dp[1][5] = 10 (seleccionar 5 objetos 0, valor 2×5=10), coincide con la solución óptima de la mochila completa.
3.2 Implementación del Código
import java.util.*;
public class SolucionMochila {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Entrada: n=número de objetos, capacidadMochila=capacidad total
int n = sc.nextInt(), capacidadMochila = sc.nextInt();
// Definir arrays de peso y valor, longitud igual al número de objetos
int[] pesos = new int[n]; // Almacena el peso de cada objeto
int[] valores = new int[n]; // Almacena el valor de cada objeto
// Entrada de pesos y valores para n objetos (cada línea: peso y valor)
for(int i = 0; i < n; i++) {
pesos[i] = sc.nextInt();
valores[i] = sc.nextInt();
}
// 1. Definir matriz dp bidimensional: dp[i][j] representa el valor máximo con los primeros i+1 objetos y capacidad j
// Filas: 0~n-1 (objetos), Columnas: 0~capacidadMochila (capacidad)
int[][] dp = new int[n][capacidadMochila + 1];
// 2. Inicializar matriz dp: cuando la capacidad es 0, el valor es 0 para todas las combinaciones
for(int i = 0; i < n ; i++) {
dp[i][0] = 0;
}
// Inicializar primera fila (solo primer objeto, se puede seleccionar infinitamente)
// Cuando capacidad >= peso del primer objeto, valor = cantidad máxima × valor[0]
for(int j = pesos[0]; j <= capacidadMochila; j++) {
dp[0][j] = dp[0][j - pesos[0]] + valores[0];
}
// 3. Orden de recorrido: bucle externo para objetos (i desde 1), bucle interno para capacidad (orden normal)
// Recorrer del segundo al n-ésimo objeto (i de 1 a n-1)
for(int i = 1; i < n; i++) {
// Recorrer todas las capacidades (0~capacidadMochila, orden normal)
for(int j = 0; j <= capacidadMochila; j++) {
// 4. Ecuación de transición de estados
if(j < pesos[i]) {
// Capacidad insuficiente, no se puede incluir objeto i, heredar resultado de fila anterior
dp[i][j] = dp[i-1][j];
} else {
// Capacidad suficiente: máximo entre "no incluir objeto i" o "incluir objeto i (se puede repetir)"
// No incluir: dp[i-1][j] (resultado de fila anterior)
// Incluir: dp[i][j-pesos[i]] + valores[i] (resultado de fila actual, permite repetición)
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-pesos[i]] + valores[i]);
}
}
}
// 5. Resultado: valor máximo con n objetos y capacidadMochila
System.out.println(dp[n-1][capacidadMochila]);
sc.close(); // Cerrar scanner
}
}
- Problema de Cambio de Monedas II
4.1 Enfoque
Paso 1:
Significado de dp[i][j] y sus índices dp[i][j] representa: usando las primeras i+1 monedas (del 0 al i), el número de formas de combinar para alcanzar el monto j; Índice i: corresponde al índice de la moneda (0longitud-1), indica "hasta qué tipo de moneda se considera"; Índice j: corresponde al monto objetivo (0monto), indica "monto a combinar"; Inicialización clave: dp[i][0] = 1 (número de formas para combinar monto 0 es 1: no seleccionar ninguna moneda) → base para contar combinaciones.
Paso 2:
if(j >= monedas[i]) { // Monto suficiente: número de combinaciones = sin usar moneda i + usando moneda i dp[i][j] = dp[i-1][j] + dp[i][j - monedas[i]]; } else { // Monto insuficiente: solo se puede omitir moneda i, heredar resultado de fila anterior dp[i][j] = dp[i-1][j]; } Desglose: dp[i-1][j]: sin usar moneda i → número de formas para combinar monto j = usando solo monedas 0i-1; dp[i][j - monedas[i]]: usando moneda i → como las monedas se pueden usar infinitamente, número de formas para combinar monto j = usando monedas 0i para combinar j-monedas[i] (reutilizar resultado de fila actual, permite "selección infinita"); +: número de combinaciones se acumula (no se toma max), porque el objetivo es "contar cuántas formas".
Paso 3:
Base 1: combinar monto 0 → dp[i][0] = 1 (todas las filas, columna 0 = 1): sin importar cuántas monedas, solo hay 1 forma de combinar 0 (no seleccionar ninguna); Base 2: solo primera moneda (i=0) → recorrer monto j (0~monto): Si j % monedas[0] == 0 (j es divisible por primera moneda): número de combinaciones es 1 (usar solo primera moneda); Si j % monedas[0] != 0: número de combinaciones es 0 (no se puede combinar); Adición: valor predeterminado de matriz es 0, no es necesario asignar cuando j % monedas[0] != 0.
Paso 4:
Bucle externo (monedas): i de 1 a longitud-1 → recorrer en orden de tipos de moneda, ya que dp[i][j] depende de dp[i-1][j] (sin moneda actual) y dp[i][j-monedas[i]] (con moneda actual); Bucle interno (monto): j de 0 a monto → recorrer en orden normal (característica de mochila completa, permite repetición de monedas); Clave: problema de combinación con mochila completa bidimensional, primero recorrer monedas, luego monto → asegura que las combinaciones no consideren orden (por ejemplo, "1+2" y "2+1" se consideran la misma combinación).
Paso 5:
Caso de prueba: monto=5, monedas=[1,2,5] (objetivo: número de formas para combinar 5 es 4); inicialización: dp[i][0] = 1 (todas las filas, columna 0 = 1); Solo primera moneda (monedas[0]=1): todos los montos j son divisibles por 1, así que dp[0][j] = 1 (j=05); → dp[0] = [1,1,1,1,1,1]. Recorrer segunda moneda (monedas[1]=2) Calcular cada monto j: j=0: dp[1][0] = 1; j=1: j<2 → dp[1][1] = dp[0][1] = 1; j=2: j≥2 → dp[1][2] = dp[0][2] + dp[1][0] = 1+1=2; j=3: j≥2 → dp[1][3] = dp[0][3] + dp[1][1] =1+1=2; j=4: j≥2 → dp[1][4] = dp[0][4] + dp[1][2] =1+2=3; j=5: j≥2 → dp[1][5] = dp[0][5] + dp[1][3] =1+2=3; → dp[1] = [1,1,2,2,3,3]. Recorrer tercera moneda (monedas[2]=5) Calcular cada monto j: j=0: dp[2][0] = 1; j=14: j<5 → heredar dp[1][j] → 1,2,2,3 respectivamente; j=5: j≥5 → dp[2][5] = dp[1][5] + dp[2][0] =3+1=4; → dp[2][5] =4 (resultado final, coincide con lo esperado).
4.2 Implementación del Código
class SolucionCambioMonedas {
public int calcularCombinaciones(int monto, int[] monedas) {
// Manejo de bordes: si array de monedas es vacío, solo monto 0 devuelve 1
if (monedas == null) {
return monto == 0 ? 1 : 0;
}
int longitud = monedas.length;
// 1. Definir matriz dp bidimensional: dp[i][j] representa número de formas con primeras i+1 monedas para monto j
int[][] dp = new int[longitud][monto + 1];
// 2. Inicializar matriz dp:
// Base 1: combinar monto 0 tiene 1 forma (no seleccionar ninguna moneda), todas las filas columna 0 = 1
for(int i = 0; i < longitud; i++) {
dp[i][0] = 1;
}
// Base 2: solo primera moneda, inicializar número de combinaciones
for(int j = 0; j <= monto; j++) {
// Corregir error: verificar si monto j es divisible por primera moneda, no por monto total
if(j % monedas[0] == 0) {
dp[0][j] = 1; // divisible, solo 1 forma (usar solo primera moneda)
}
// No divisible, valor predeterminado 0, no es necesario asignar
}
// 3. Orden de recorrido: bucle externo para monedas (i desde 1), bucle interno para monto (orden normal)
// Recorrer del segundo al último tipo de moneda (i de 1 a longitud-1)
for(int i = 1; i < longitud; i++) {
// Recorrer todos los montos (0~monto, orden normal para mochila completa)
for(int j = 0; j <= monto; j++) {
// 4. Ecuación de transición de estados
if(j >= monedas[i]) {
// Monto suficiente:
// dp[i-1][j] = número de formas sin moneda i (resultado fila anterior)
// dp[i][j-monedas[i]] = número de formas con moneda i (resultado fila actual, permite repetición)
// Acumular número de combinaciones (no tomar max)
dp[i][j] = dp[i-1][j] + dp[i][j - monedas[i]];
} else {
// Monto insuficiente: solo se puede omitir moneda i, heredar resultado fila anterior
dp[i][j] = dp[i-1][j];
}
}
}
// 5. Devolver resultado: número de formas para combinar monto con todas las monedas
return dp[longitud - 1][monto];
}
}
4.3 Array dp Unidimensional
class SolucionCambioMonedasUnidimensional {
public int calcularCombinaciones(int monto, int[] monedas) {
// Manejo de bordes: si array de monedas es vacío, solo monto 0 devuelve 1
if (monedas == null) {
return monto == 0 ? 1 : 0;
}
// 1. Definir array dp unidimensional: dp[j] representa número de formas para combinar monto j
int[] dp = new int[monto + 1];
// 2. Inicializar: combinar monto 0 tiene 1 forma (base de conteo)
dp[0] = 1;
// 3. Orden de recorrido: bucle externo para monedas (primero monedas), bucle interno para monto (orden normal)
for (int moneda : monedas) { // Recorrer cada tipo de moneda
// Bucle interno: recorrer montos en orden normal (de moneda a monto), permite "uso infinito" de monedas
for (int j = moneda; j <= monto; j++) {
// 4. Ecuación de transición de estados:
// dp[j] (antes de actualizar) = número de formas sin moneda actual
// dp[j - moneda] = número de formas con moneda actual (recorrido normal ya actualizado, permite uso infinito)
// Acumular ambos para obtener nuevo número de combinaciones
dp[j] += dp[j - moneda];
}
}
// 5. Devolver resultado: número de formas para combinar monto
return dp[monto];
}
}
La lógica central del orden de recorrido en array dp unidimensional se puede resumir como: el recorrido inverso de capacidad es requerido en mochila 0-1 para, al utilizar resultados de dp de la ronda anterior sin seleccionar el objeto actual, asegurar que cada objeto solo se seleccione una vez; el recorrido normal de capacidad es requerido en mochila completa para, al utilizar resultados de dp de la ronda actual con el objeto seleccionado, permitir la selección infinita de objetos. La elección del orden de recorrido está determinada completamente por "si el objeto se puede seleccionar repetidamente" — en mochila 0-1 (como subconjunto con suma igual, suma objetivo) se requiere orden inverso para evitar selección repetida, en mochila completa (como última piedra II, cambio de monedas II) se requiere orden normal para permitir selección infinita, y el problema de cambio de monedas II como problema de combinación con mochila completa naturalmente adopta recorrido normal para permitir el uso infinito de monedas, mientras que el orden externo primero monedas luego monto interno también asegura que se contabilicen combinaciones sin considerar orden, no permutaciones.
Si se busca número de combinaciones, el bucle externo recorre objetos, el bucle interno recorre la mochila.
Si se busca número de permutaciones, el bucle externo recorre la mochila, el bucle interno recorre objetos.
- Problema de Suma de Combinaciones IV
5.1 Enfoque
Paso 1:
Significado de dp[i] y su índice dp[i] representa: el número de permutaciones para alcanzar el valor objetivo i (permutaciones, considerando el orden de los números); Índice i: corresponde al valor objetivo (0~objetivo), por ejemplo dp[3] = 4 significa "hay 4 permutaciones para sumar 3: 1+1+1, 1+2, 2+1, 3" (asumiendo nums=[1,2,3]); Inicialización clave: dp[0] = 1 (número de permutaciones para objetivo 0 es 1: no seleccionar ningún número, base para contar permutaciones).
Paso 2:
if(i >= nums[j]) { dp[i] += dp[i - nums[j]]; } Bucle externo i: recorre valores objetivos (de 0 a objetivo), indica "el valor objetivo actual a combinar"; Bucle interno j: recorre cada número en el array nums, indica "intentar usar nums[j] como último número de la permutación"; Condición i >= nums[j]: el objetivo i es lo suficientemente grande para incluir nums[j] como último número; Lógica central: número de permutaciones para objetivo i = suma de "todas las permutaciones que terminan con nums[j] y combinan i-nums[j]" para todos los j posibles. Comprensión esencial de la ecuación de transición: el += es "acumulación de permutaciones" — porque las permutaciones consideran orden, cada número puede ser el "último paso", por lo que se deben sumar todas las permutaciones posibles del "último paso", lo cual es completamente opuesto a la lógica de combinaciones "seleccionar números primero luego combinar monto".
Paso 3:
dp[0] = 1: debe inicializarse explícitamente, es la "base de conteo" para permutaciones (sin esta base, todas las permutaciones serían 0); Otros dp[i] (i>0): valor inicial 0, indica "en estado inicial, no hay permutación que alcance i".
Paso 4:
Bucle externo: recorre valores objetivo i (0~objetivo) → corresponde a "recorrer capacidad" en suma de combinaciones IV; Bucle interno: recorre números nums[j] → corresponde a "recorrer objetos" en suma de combinaciones IV; Razón clave: primero capacidad luego objetos, permite contar "diferentes órdenes" en permutaciones — por ejemplo, al combinar 3, procesando primero i=1 (número 1), i=2 (número 2), luego i=3, se pueden contar tanto "1+2" como "2+1"; si fuera como en cambio de monedas II primero objetos luego capacidad, solo se contarían combinaciones (sin distinguir orden).
Paso 5:
Ejemplo de derivación de dp array (nums=[1,2], objetivo=3) Inicialización: dp = [1,0,0,0]; Recorrer i=0: ningún nums[j] cumple i>=nums[j], dp[0] permanece 1; Recorrer i=1: j=0 (nums[j]=1): i>=1 → dp[1] += dp[0] → dp[1]=1; j=1 (nums[j]=2): i<2 → sin actualización; → dp = [1,1,0,0]; Recorrer i=2: j=0 (nums[j]=1): i>=1 → dp[2] += dp[1] → dp[2]=1; j=1 (nums[j]=2): i>=2 → dp[2] += dp[0] → dp[2]=2; → dp = [1,1,2,0]; Recorrer i=3: j=0 (nums[j]=1): i>=1 → dp[3] += dp[2] → dp[3]=2; j=1 (nums[j]=2): i>=2 → dp[3] += dp[1] → dp[3]=3; → dp = [1,1,2,3]; Resultado final dp[3]=3 (permutaciones: 1+1+1, 1+2, 2+1), coincide con lo esperado.
5.2 Implementación del Código
class SolucionSumaCombinaciones {
public int contarPermutaciones(int[] nums, int objetivo) {
// 1. Definir array dp unidimensional: dp[i] representa número de permutaciones para valor objetivo i
int[] dp = new int[objetivo + 1];
// 2. Inicializar: dp[0] = 1 (permutaciones para objetivo 0 es 1, base de conteo)
dp[0] = 1;
// 3. Orden de recorrido: bucle externo para valores objetivo (capacidad), bucle interno para números (objetos) → contar permutaciones
// Bucle externo: recorrer todos los valores objetivo (0~objetivo)
for(int i = 0; i <= objetivo; i++) {
// Bucle interno: recorrer cada número en el array (intentar usarlo como último número de la permutación)
for(int j = 0; j < nums.length; j++) {
// 4. Ecuación de transición de estados:
// Condición: valor objetivo actual i >= número nums[j] (puede incluirlo como último número)
if( i >= nums[j]) {
// dp[i] (antes de actualizar): número de permutaciones sin incluir el número actual
// dp[i - nums[j]]: número de permutaciones para i-nums[j], añadiendo nums[j] al final, se obtiene nueva permutación para i
// Acumular números de permutaciones para todos los números posibles, obteniendo total
dp[i] += dp[i - nums[j]];
}
}
}
// 5. Devolver resultado: número de permutaciones para objetivo
return dp[objetivo];
}
}
- Problema de Escaleras Avanzado
6.1 Enfoque
Paso 1:
dp[i] representa: número de métodos diferentes para llegar al escalón i (considerando orden, por ejemplo 1+2 y 2+1 son métodos diferentes); Índice i: corresponde al número de escalón (0~n), por ejemplo dp[3] = 3 significa hay 3 métodos para llegar al escalón 3; Enicialización clave: dp[0] = 1 (métodos para llegar al escalón 0 es 1: quedarse en el mismo lugar, base de conteo, igual que dp[0]=1 en suma de combinaciones IV).
Paso 2:
if(i >= j) { dp[i] += dp[i-j]; } Bucle externo i: recorre escalones a subir (1n), indica "actualmente se intenta llegar al escalón i"; Bucle interno j: recorre pasos posibles (1m), indica "último paso de j escalones"; Condición i >= j: el escalón i es lo suficientemente alto para llegar con "último paso de j escalones"; Lógica central: métodos para llegar al escalón i = suma de "todos los métodos que llegan a i-j escalones más un último paso de j escalones" para todos los j posibles.
Paso 3:
dp[0] = 1: debe inicializarse explícitamente, es la "base de conteo" (por ejemplo, al subir 1 escalón, j=1 → dp[1] += dp[0] → 1 método); Otros dp[i] (i>0): valor inicial 0 (valor predeterminado de array), indica "en estado inicial, no hay métodos para llegar al escalón i".
Paso 4:
Bucle externo: recorre escalones i (1n) → corresponde a "recorrer capacidad" en suma de combinaciones IV; Bucle interno: recorre pasos j (1m) → corresponde a "recorrer objetos" en suma de combinaciones IV; Clave: primero escalones luego pasos, asegura que se cuenten permutaciones (distinguiendo 1+2 y 2+1) — si fuera al contrario primero pasos luego escalones, se convertiría en combinaciones (1+2 y 2+1 contaría como 1), lo cual sería incorrecto.
Paso 5:
Ejemplo de derivación de dp array (n=3, m=2) Inicialización: dp = [1,0,0,0]; Recorrer i=1 (subir 1 escalón): j=1: i≥1 → dp[1] += dp[0] → dp[1]=1; j=2: i<2 → sin actualización; → dp = [1,1,0,0]; Recorrer i=2 (subir 2 escalones): j=1: i≥1 → dp[2] += dp[1] → dp[2]=1; j=2: i≥2 → dp[2] += dp[0] → dp[2]=2; → dp = [1,1,2,0]; Recorrer i=3 (subir 3 escalones): j=1: i≥1 → dp[3] += dp[2] → dp[3]=2; j=2: i≥2 → dp[3] += dp[1] → dp[3]=3; → dp = [1,1,2,3]; Resultado final dp[3]=3, coincide con la salida del ejemplo.
6.2 Implementación del Código
import java.lang.*;
import java.util.*;
public class SolucionEscaleras {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // Número total de escalones (corresponde a objetivo en suma de combinaciones IV)
int m = sc.nextInt(); // Máximo número de escalones por paso (corresponde a nums=[1,2,...,m] en suma de combinaciones IV)
// 1. Definir array dp: dp[i] representa número de métodos para llegar al escalón i (permutaciones)
int[] dp = new int[n + 1];
// 2. Inicializar: dp[0]=1 (métodos para llegar al escalón 0 es 1, base de conteo)
dp[0] = 1;
// 3. Orden de recorrido: bucle externo para escalones (capacidad), bucle interno para pasos (objetos) → contar permutaciones
// Bucle externo: recorrer escalones a subir (1~n)
for(int i = 1; i <= n; i++) {
// Bucle interno: recorrer pasos posibles (1~m)
for(int j = 1; j <= m; j++) {
// 4. Ecuación de transición de estados:
// Condición: escalón actual i ≥ último paso j (se puede llegar con ese paso)
if(i >= j) {
// dp[i] (antes de actualizar): métodos sin incluir "último paso de j escalones"
// dp[i-j]: métodos para llegar a i-j escalones, más último paso j escalones, son nuevos métodos para llegar a i
// Acumular métodos para todos los pasos posibles, obteniendo total
dp[i] += dp[i-j];
}
}
}
// 5. Resultado: número de métodos para llegar al escalón n
System.out.println(dp[n]);
sc.close();
}
}