Somma minima del percorso
Data una griglia di altezza h e larghezza w riempita con numeri interi, si vuole trovare un percorso dall’angolo in alto a sinistra all’angolo in basso a destra che minimizzi la somma dei numeri incontrati. È consentito spostarsi solo verso destra o verso il basso.
3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Input
La prima riga dell’input contiene due interi h e w (1 ≤ h, w ≤ 1000).
Le successive h righe contengono w numeri interi separati da spazio , che rappresentano i valori nella griglia .
Output
Il programma deve stampare la somma minima possibile per muoversi dall’angolo in alto a sinistra a quello in basso a destra.
Examples
Input | Output |
|---|---|
3 4 3 2 1 3 1 9 2 3 9 1 5 4 | 15 |
Explanation
Possiamo seguire il percorso: 3 → 2 → 1 → 2 → 3 → 4
Suggerimento 1
Lo stato in un problema di programmazione dinamica può essere rappresentato come un array bidimensionale.
Suggerimento 2
Questo array può rappresentare la soluzione ottimale fino a una certa coordinata (d[r][c] indica il miglior percorso per arrivare alla riga r e colonna c).
Perché l’approccio greedy non funziona in questo caso? Immagina di muoverti sempre nella direzione con il valore più piccolo: quale sarebbe il problema?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB