Anzahl der Möglichkeiten, N Schritte zu erreichen

Question

Also machte ich diese einfache dynamische Programmierung Frage über das Erreichen der n Schritt, während nur in der Lage, 1 oder 2 Schritte auf einmal zu gehen. Ich weiß, die Antwort ist im Grunde eine Fibonacci Sequenz und die Antwort ist: # Schritte zu erreichen n-2 + # Schritte zu erreichen n-1.

T(n) = T(n-1) + T(n-2); 

Je mehr ich darüber nachdenke, desto weniger sicher war ich. Sollte es am Ende keinen zusätzlichen Schritt geben, um den Schritt n selbst zu erreichen? Offensichtlich funktioniert es, wenn ich Zahlen anschließe, aber ich frage mich, warum es am Ende keinen zusätzlichen Schritt gibt, um zu signalisieren, dass tatsächlich n anstelle von n-1 und n-2 erreicht wird.

Answer 1

Hier finden wir Anzahl der Möglichkeiten N Stufen zu erreichen. Recht? Wir finden nicht Anzahl der Züge. (Lassen Sie uns sagen, in jedem Zug können Sie einen oder zwei Schritte machen.)

n th erreichen SPEP der vorherigen Schritt kann n-1 ten Schritt oder n-2 ten Schritt werden erreicht. Dies sind zwei verschiedene Wege zu erreichen n. Geht man von n-1 zu n oder von n-2 zu n, kommt ein weiterer Schritt hinzu. Aber es ist das gleiche Weg.