Wyjaśnić ten dynamiczny wspinaczki programowania n-schodek kodu

Question

Problem jest

„Jesteś wspinaczki przypadku schodów. Za każdym razem, gdy można albo zrobić 1 krok lub 2 kroki. Klatka schodowa ma n kroków. Na ile różnych sposobów można wspinasz się po schodach? "

Poniżej przedstawiono rozwiązanie kodu dla tego problemu, ale mam problemy z jego zrozumieniem. Czy ktoś może wyjaśnić mi

int stairs(int n) { 
    if (n == 0) return 0; 
    int a = 1; 
    int b = 1; 
    for (int i = 1; i < n; i++) { 
    int c = a; 
    a = b; 
    b += c; 
    } 
    return b; 
} 

Dzięki,

Answer 1

Cóż, najpierw trzeba zrozumieć rekurencyjnego wzoru, oraz w jaki sposób iteracyjny pochodzi z jednego z niego.

rekurencyjne formuła:

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

(f(n-1) w jednym etapie, w dwóch etapach f(n-2) i całkowitej liczby oznacza liczbę sposobów zastosowania jednego z nich - więc sumy).

Jeśli przyjrzysz się uważnie - jest to również dobrze znana seria - fibonacci numbers, a rozwiązaniem jest po prostu obliczanie każdej liczby, ale zamiast ponownie obliczać rekursję, co daje znacznie bardziej wydajne rozwiązanie.