Java dynamische Programmierung "Climbing Stairs", verstehe nicht die Logik

Question

Frage ist: Sie klettern eine Treppe Fall. Es dauert n Stufen, um nach oben zu gelangen. Jedes Mal können Sie entweder 1 oder 2 Stufen klettern. Auf wie viele verschiedene Arten kannst du nach oben klettern?

Und ich sah einen Java-Code, der richtig ist, aber ich verstehe die Logik nicht. Kann mir das jemand erklären? Was ist a, b, c Stand von?

public int climbStairs(int n) { 

    if (n<2) return 1; 

    int a = 1; 
    int b = 1; 
    int c = 1; 

    for (int i=2; i<=n; i++){ 
     c = b; 
     b = a + b; 
     a = c; 
    } 
    return b; 
} 

Answer 1

Die rekursive Formel

f(n) = f(n-1) + f(n-2) 
f(0) = f(1) = 1 

---

Übersetzt in a, b, c im Code

if (n<2) return 1; 

int a = 1; 
int b = 1; 
int c = 1; 

Die oben definiert und berechnet unter f(0) = f(1) = 1f(n) = f(n-1) + f(n-2) für n >= 2

012.351.

for (int i=2; i<=n; i++){ 
    c = b;  // f(i-1) is temporary saved in c 
    b = a + b; // f(i-2) + f(i-1) is saved in b 
    a = c;  // f(i-1) is saved in a for the next iteration 
} 

Answer 2

Der Code selbst ist im Grunde ein Fibonacci-Nummerngenerator.

int a = 1; 
int b = 1; 
int c = 1; 

for (int i=2; i<=n; i++){ 
    c = b; 
    b = a + b; 
    a = c; 
} 

schafft die n th Fibonacci-Zahl, wobei 1 für n = 0 beginnen. Die wichtigere Frage:
Wie entspricht die Anzahl der möglichen Wege der Fibonacci-Reihe?

Für n = 0 und n = 1 ist die Antwort ziemlich einfach: Es gibt genau einen Weg: nicht bewegen (0), einen einzigen Schritt (1) machen. Für jeden anderen n können wir einen rekursiven Ansatz verwenden: Es gibt zwei Möglichkeiten, um den Schritt n zu erreichen: machen Sie einen kurzen Schritt von n - 1 oder einen langen Schritt von n - 2. Das ist das gleiche wie die Fibonacci-Sequenz: fib(n + 2) = fib(n + 1) + fib(n).