Minimale Pfadsumme
Gegeben ist ein Gitter der Höhe
h und Breite w, das mit ganzen Zahlen gefüllt ist. Gesucht wird ein Pfad von der linken oberen Ecke bis zur rechten unteren Ecke, bei dem die Summe der Zahlen entlang des Pfads minimiert wird. Dabei darf man sich nur nach rechts oder nach unten bewegen.3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
h und w (1 ≤ h, w ≤ 1000).Die nächsten
h Zeilen enthalten jeweils w durch Leerzeichen getrennte ganze Zahlen , die die Werte im Gitter repräsentieren .Ausgabe
Das Programm soll die kleinstmögliche Summe ausgeben, um von der oberen linken Ecke bis zur unteren rechten Ecke zu gelangen.
Beispiele
Input | Output |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
Erklärung
Wir können uns zum Beispiel folgendermaßen bewegen: 3 → 2 → 1 → 2 → 3 → 4
Hint 1
Der Status in einem dynamischen Programm kann in einem zweidimensionalen Array abgebildet werden.
Hint 2
Dieses Array kann die jeweils beste mögliche Lösung bis zu den entsprechenden Koordinaten repräsentieren (z. B.
d[r][c] für den besten Pfad, um Zeile r und Spalte c zu erreichen).Warum funktioniert ein gieriger Ansatz hier nicht? Stell dir vor, du würdest dich immer in Richtung des kleinsten Werts bewegen. Worin läge das Problem dabei?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB