[RUBY] Informationen zur dynamischen Planungsmethode (Top-Down-Methode, Memokonvertierung, eindimensional)

Wenn ich Paiza oder AtCoder mache, gibt es einige Dinge, die ich als Programm schreiben sollte, aber die Verarbeitungszeit ist langsam und knapp, daher denke ich darüber nach, diese dynamische Planungsmethode kennenzulernen und die Verarbeitungsgeschwindigkeit zu verbessern. Es ist jedoch schwer zu verstehen, daher werde ich es schrittweise verbalisieren.

Definition der dynamischen Planungsmethode

• Verwendung von induktiven Beziehungen
• Aufzeichnung der Berechnungsergebnisse

Es scheint ein allgemeiner Begriff für Algorithmen zu sein, die zufrieden stellen (Wikipedia). Die geltenden Bedingungen usw. werden vorerst weggelassen. Zum leichteren Verständnis ist es eine Methode, den Rechenaufwand zu reduzieren, indem die induktive Beziehung in Form eines allmählichen Ausdrucks beschrieben, das Berechnungsergebnis hier aufgezeichnet und unter Bezugnahme auf das Ergebnis berechnet wird. ..

Ja, ich kann es überhaupt nicht sagen. Gehen wir zu einem konkreten Beispiel (feste Fibonacci-Zahlenfolge). Die Fibonacci-Zahlenfolge ist eine allgemeine Lösung der graduellen Gleichung, dargestellt durch a [0] = a [1] = 1, a [n] = a [n-1] + a [n-2]. (Die Summe der beiden vorhergehenden bestimmt den Wert dieses Begriffs)

Beim normalen Schreiben

fib.rb

def fib(n)
  if n <=1
    return 1
  else
    fib(n-1)+fib(n-2)
  end
end

n=gets.chomp.to_i
puts fib(n)

So was. In diesem Fall beträgt der Berechnungsbetrag O (2 ^ n), und wenn der n zugewiesene Wert klein ist, gibt es kein Problem, aber es wird ab etwa 40 schwierig.

Bei dynamischer Planung (von oben nach unten)

fib2.rb

@dp=[]
def fib2(n)
  if n <= 1
    return 1
  else
    if @dp[n]
      return @dp[n]
    else
      @dp[n] = fib2(n-1)+fib2(n-2)
    end
  end
end
n=gets.chomp.to_i
puts fib2(n)

Bereiten Sie ein Array mit dem Namen @dp vor (n wird in einem Bild wie ein Hash eines Schlüssels verwendet) und speichern Sie die Berechnungsergebnisse in diesem Array. Zum Zeitpunkt der Berechnung wird der Berechnungsbetrag unter Bezugnahme auf die Werte aus diesem Array zu O (n), und der Berechnungsbetrag wird drastisch reduziert. In diesem Fall ist es ein Moment, selbst wenn Sie n durch 10000 ersetzen.

Ergänzung

Verwenden Sie beim Definieren eines Arrays Instanzvariablen.

Schließlich

Ich konnte mein Verständnis nicht einholen, deshalb werde ich versuchen, es in kleinen Mengen auszugeben, während ich viel lerne.

Referenzartikel

https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95 https://www.jabba.cloud/20161020172918/