Dynamische Programmierung rekursiv oder iterativ

Dynamische Programmierung kann (in vielen Fällen) als rekursive Lösung in umgekehrter Richtung gesehen werden.

Normalerweise würden Sie in einer Rekursion x(n+1) = f(x(n)) mit einer Stopbedingung für n=0 (oder einen anderen Wert) berechnen.

In vielen Fällen ist die Funktion f eine Min / Max-Funktion, aber das muss nicht sein. Außerdem muss die Funktion keine einzelne Variable enthalten.

Dynamische Programmierung würde dieses Problem lösen, indem Sie f(0) , dann f(1) , dann f(2) etc.

Bei mehr als einer Variablen gibt es normalerweise eine natürliche Reihenfolge, um die Funktion zu berechnen.

Ein Beispiel, das dynamische Programmierung lösen kann: Sie erhalten 3 Golfschläger. Jeder Golfschläger kann einen Golfball x Distanzeinheiten vorwärts schicken (zum Beispiel 24, 37 und 54 Einheiten). Die Frage ist: Kann man ein Loch treffen, das genau 200 Einheiten entfernt ist? Und wenn Sie können, was ist die minimale Anzahl von Schüssen, die Sie brauchen.

Die rekursive Lösung wäre etwa so:

Dies würde eine triviale Implementierung ermöglichen, wobei die Funktion shot(n) 0 zurückgibt, wenn n 0 ist, eine große Zahl, wenn n kleiner als 0 ist, und der obige Ausdruck andernfalls.

Bei großen Werten von n treffen Sie jedoch immer wieder dieselben Werte aus verschiedenen Zweigen des obigen Ausdrucks. In diesem Fall ist es besser, nur bei 0 zu beginnen und shots(0) , shots(1) , shots(2) usw. zu berechnen. Dies wäre die "dynamische Programmierung" Lösung für dieses Problem - mit linearer Zeit und konstantem Raum statt exponentieller Zeit ( durch einen 3-Wege-Baum) und bestenfalls linearen Raum (für den Call-Stack).