Lösungsskizze DVD
=================

Bis zu 50 Punkte bekommen wir, indem wir die Reihenfolge aller Videotheken systematisch durchprobieren. Alle möglichen Reihenfolgen durchzuprobieren in O(N!) gibt 30 Punkte. Wenn wir bemerken, dass wir in jedem Schritt entweder die nächstgelegene, unbesuchte Videothek links oder rechts hinzunehmen, dann können wir die Laufzeit auf O(2^N) reduzieren, was 50 Punkte gibt.

Für die volle Punktzahl muss man eine Lösung mittels dynamischer Programmierung suchen. Die Frage dazu ist:
Wenn wir annehmen, dass wir von Ron's Haus aus die ersten l Häuser nach links und die ersten r Häuser nach rechts besucht haben und uns jetzt am linkesten/rechtesten Haus davon befinden, was ist dann die minimale Ausleihgebühr, die wir bis dahin angesammelt haben können? (inklusiv der schon angesammelten Gebühren, für die noch nicht retournierten DVDs).
Diesen Zustand können wir nun leicht auf einen von zwei Vorgängerzuständen zurückführen: Der Zustand unmittelbar vor dem aktuellen Zustand, war der, dass Peter die selben Videotheken besucht hat, wie jetzt, einfach ohne die allerletzte, und er sich entweder ganz links oder ganz rechts davon befand. Wenn wir diese beiden Teillösungen vorberechnet haben, können wir sie leicht zur Lösung für den gesamten Bereich kombinieren: Die billigere von beiden Varianten wird bevorzugt. So berechnen wir die günstigste Lösung um alle Videotheken zu besuchen, unabhängig davon, wo Ron sich am Schluss befindet.

Viele von euch haben versucht diese Aufgabe greedy zu lösen und Ron einfach immer Schritt für Schritt zur nächstgelegenen Videothek gehen lassen. Dies ist aber nicht korrekt, wie wir an folgendem Beispiel leicht sehen können:
Wir nehmen an, es hat je eine Videothek mit einer ausgeliehenen DVD an folgenden Positionen:
-2, 1, 2, 4, 8, 16, 32, ..., 2ˆ(n-1)
Mit einer Greedy-Strategie besucht Stofl so zuerst Videothek 1, dann 2, 4 usw. und muss am Schluss nochmals ganz zurück zur -2, was eine Gebühr von über 2^n für diese letzte DVD bedeutet. Hätte er diesen kleinen Umweg zur -2 zuerst gemacht, so hätten alle anderen DVD lediglich 4 Franken mehr gekostet, was lediglich Zusatzkosten von 4n verursacht.

Speicher: O(N^2)
Laufzeit: O(N^2)