Kann jeder rekursive Algorithmus mit dynamischer Programmierung verbessert werden?

Question

Ich bin ein Student im ersten Jahr CSC Student, der in wettbewerbsfähige Programmierung zu bekommen sucht.

Rekursion beinhaltet die Definition und Lösung von Teilproblemen. Soweit ich weiß, beinhaltet top-down dynamic programming (dp) das Memoisieren der Lösungen für Subprobleme, um die zeitliche Komplexität des Algorithmus zu reduzieren.

Kann Top-Down-DP verwendet werden, um die Effizienz von alle rekursiven Algorithmus mit überlappenden Subproblemen zu verbessern? Wo würde dp nicht funktionieren und wie kann ich das erkennen?

Answer 1

Die kurze Antwort ist: Ja.

Allerdings gibt es einige Einschränkungen. Der offensichtlichste ist, dass sich rekursive Aufrufe überlappen müssen. I.e. Während der Ausführung eines Algorithmus muss die rekursive Funktion mehrfach mit den gleichen Parametern aufgerufen werden. Auf diese Weise können Sie den Rekursionsbaum durch Memoisierung abschneiden. Daher können Sie Memoization immer verwenden, um die Anzahl der Anrufe zu reduzieren.

Diese Reduzierung der Anrufe kommt jedoch mit einem Preis. Sie müssen die Ergebnisse irgendwo speichern. Die nächste offensichtliche Einschränkung ist, dass Sie genügend Speicher haben müssen. Dies kommt mit einer nicht so offensichtlichen Einschränkung. Der Speicherzugriff benötigt immer etwas Zeit. Sie müssen zuerst herausfinden, wo das Ergebnis gespeichert ist, und es vielleicht sogar an einen Ort kopieren. In einigen Fällen kann es daher schneller sein, dass die Rekursion das Ergebnis berechnet, anstatt es von irgendwo zu laden. Dies ist jedoch sehr implementierungsspezifisch und kann sogar von der Betriebssystem- und Hardware-Konfiguration abhängen.