Suma mínima de trayectoria
Dada una cuadrícula de altura
h y ancho w llena de números enteros, se te pide encontrar un camino desde la esquina superior izquierda hasta la esquina inferior derecha que minimice la suma de los valores recorridos. Solo se permite moverse hacia la derecha o hacia abajo.3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Entrada
La primera línea de la entrada contiene dos números enteros
h y w (1 ≤ h, w ≤ 1000).Las siguientes
h líneas contienen w números enteros separados por espacios , que representan los valores en la cuadrícula .Salida
El programa debe imprimir la suma mínima posible para llegar desde la esquina superior izquierda hasta la esquina inferior derecha.
Ejemplos
Entrada | Salida |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
Explicación
Podemos recorrer: 3 → 2 → 1 → 2 → 3 → 4
Sugerencia 1
El estado en un problema de programación dinámica puede ser un arreglo de dos dimensiones.
Sugerencia 2
Este arreglo puede representar la mejor solución posible hasta esa coordenada (por ejemplo,
d[r][c] representa la mejor ruta para llegar a la fila r y la columna c).¿Por qué no funciona un enfoque greedygreedy (avaricioso) en este caso? Imagina que siempre eliges moverte en la dirección del valor más pequeño posible. ¿Qué problema surgiría con esta estrategia?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB