Medio · PD
Suma mínima del camino
No puedes ir a la izquierda ni hacia arriba, así que al llegar a una celda solo has podido venir de arriba o de la izquierda — dos posibles pasados, elige el más barato. Rellena la tabla fila a fila y la esquina inferior derecha guarda la respuesta.
En una frase<code>best[i][j] = a[i][j] + min(best[i-1][j], best[i][j-1])</code>, con la primera fila y columna acumuladas — la respuesta queda en <code>best[n][m]</code>.
El problema
Entrada: La primera línea trae n y m (1 ≤ n, m ≤ 10). Luego n líneas con m enteros (0 ≤ a ≤ 100), la cuadrícula.
Salida: La suma mínima posible de las celdas de un camino desde la celda superior izquierda a la inferior derecha, moviéndose solo a la derecha o hacia abajo.
Ejemplos:
| Entrada | Salida |
|---|---|
2 2 | 3 |
3 3 | 7 |
En el ejemplo clásico de 3×3 parece que el camino correcto esquiva el 5 y el 4 — síguelo a mano: 1 → 1 → 5 es peor que 1 → 3 → 1. Los ojos son malos para esto y dos min por celda no; la tabla existe justo por eso.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Dos pasados por celda
Como está prohibido ir a la izquierda y hacia arriba, la forma más barata de estar en (i, j) es la más barata entre llegar a (i−1, j) y a (i, j−1), más el peaje a[i][j]. Esa es toda la recurrencia: best[i][j] = a[i][j] + min(best[i-1][j], best[i][j-1]).
Pista 2 — Los bordes solo tienen un pasado
En la primera fila solo puedes venir de la izquierda; en la primera columna, solo de arriba. Rellénalas por acumulación simple: best[1][j] = best[1][j-1] + a[1][j] — un bug frecuente es dejar las celdas del borde con el valor de la cuadrícula en vez de la suma acumulada.
Pista 3 — El voraz no basta — la tabla sí
Atajo tentador: en cada celda, avanzar hacia el vecino más barato. Falla — un paso algo caro puede abrir un pasillo barato. La tabla de PD nunca se arrepiente, porque calcula el óptimo real de todas las celdas antes de que se necesite cualquiera. Cuando te pique decidir localmente, cambia a una tabla.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int best[12][12];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int a;
cin >> a;
if (i == 1 && j == 1) best[i][j] = a;
else if (i == 1) best[i][j] = best[i][j - 1] + a;
else if (j == 1) best[i][j] = best[i - 1][j] + a;
else {
int up = best[i - 1][j];
int left = best[i][j - 1];
best[i][j] = (up < left ? up : left) + a;
}
}
}
cout << best[n][m] << endl;
return 0;
}Este es el patrón detrás de los problemas de caminos de cualquier forma: cambia las direcciones prohibidas, el peaje, pide el máximo — a la tabla le da igual. El primo unidimensional de «mejor valor terminando aquí» es Suma máxima de subarray, que merece leerse junto a este.
Análisis profundo
Por qué funciona
El movimiento está limitado a derecha y abajo, así que cada celda tiene exactamente dos predecesores posibles: arriba y a la izquierda. La forma más barata de estar en (i, j) es, pues, a[i][j] más la más barata de las dos llegadas — calcula eso para cada celda en orden de fila y best[n][m] es la respuesta, sin búsqueda alguna.
El coste
O(n·m) de tiempo y espacio: cada celda hace un min y una suma. Para 10×10 son 100 celdas; incluso una cuadrícula de 1000×1000 es un millón de celdas, instantáneo.
Dónde falla
- Las celdas del borde tienen un solo pasado: la primera fila debe ser una suma acumulada desde la izquierda y la primera columna desde arriba. Dejarlas con los valores de la cuadrícula es la respuesta errónea más común.
- Elegir min(up, left) y olvidar sumar a[i][j] — el peaje de cada celda es obligatorio, incluida la inicial.
- Avanzar con voraz (moverse siempre al vecino más barato) parece correcto y falla: un paso caro puede abrir un pasillo barato. La tabla nunca se arrepiente porque calcula todas las celdas antes de necesitar cualquiera.
Siguiente paso
La versión 1D de la misma idea — mejor valor terminando aquí, sin tabla — es Suma máxima de subarray. Para contar rectángulos en vez de caminos, mira Sumas por rangos 2D.
Dos cosas para recordar
- best[i][j] = a[i][j] + min(desde arriba, desde la izquierda) — dos pasados, elige uno.
- Los bordes se acumulan; no tienen segunda dirección sobre la que tomar un min.
🐞 Esta versión falla: ábrela y pruébala
Deja las celdas del borde con su valor de la cuadrícula — la primera fila nunca acumula
#include <iostream>
using namespace std;
int best[12][12];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int a;
cin >> a;
if (i == 1 && j == 1) best[i][j] = a;
else if (i == 1) best[i][j] = a; // bug: no accumulation
else if (j == 1) best[i][j] = a; // bug: no accumulation
else {
int up = best[i - 1][j];
int left = best[i][j - 1];
best[i][j] = (up < left ? up : left) + a;
}
}
}
cout << best[n][m] << endl;
return 0;
}