Programmierübung – Treppensteigen – Fibonacci-Zahlen – C++ – Online Judge

Frage: Sie steigen Treppen. Es dauert n Schritte, um an die Spitze zu gelangen. Sie können jedes Mal 1 Schritt oder 2 Schritte machen. Wie viele verschiedene Wege, um an die Spitze zu gelangen?

Problembeschreibung: http://oj.leetcode.com/problems/climbing-stairs/

Dieses Problem mag auf den ersten Blick schwierig erscheinen, aber wenn Sie eine Sekunde nachdenken, finden Sie es vielleicht so einfach. Die Antwort lautet Fibonacci-Zahlen (siehe hier, hier )

Nun, die ursprünglichen Fibonacci-Zahlen sind als Folgen definiert:

Für dieses Problem müssen wir nur ein wenig modifizieren:

und weil es für nur 1 Schritt nur 1 eindeutigen Weg gibt und wir für 2 Schritte zwei Lösungen haben: 1 + 1 oder 2.

Der Rest ist als Fibonacci-Reihe. Denn von der aktuellen Position aus sind wir möglicherweise von den beiden vorherigen Positionen F(n-1) und F(n-2).

Sie können Rekursion verwenden, aber dies kann durch eine effektivere iterative Lösung gelöst werden.

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        // f(n) = f(n - 1) + f(n - 2)
        int a = 1, b = 2, c = a + b;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

Oder Sie bevorzugen eine einfachere rekursive Funktion:

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Hinweis: Die rekursive  Funktion ergibt ZEITLIMIT ÜBERSCHRITTEN bei Test 44. Das liegt daran, dass die rekursive Funktion normalerweise viele Male Zwischenwerte berechnet. Zum Beispiel , .  wird zweimal berechnet.