Kodningsövning – Gå i trappor – Fibonacci-nummer – C++ – Onlinedomare

Fråga: Du går i trappor. Det tar n steg för att komma till toppen. Varje gång kan du ta 1 steg eller 2 steg. Hur många olika sätt att ta sig till toppen?

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

Det här problemet kan se svårt ut i början, men när du tänker efter en sekund kanske du tycker att det är så lätt. Svaret är Fibonacci Numbers (se här, här )

Tja, de ursprungliga Fibonacci-numren definieras som sekvenser:

För detta problem måste vi bara ändra lite:

och eftersom för endast 1 steg finns det bara 1 distinkt sätt och för 2 steg har vi två lösningar: 1 + 1 eller 2.

Resten är som Fibonacci-serien. Eftersom från den aktuella positionen är vi möjligen från tidigare två positioner, F(n-1) och F(n-2).

Du kan använda rekursion, men detta kan lösas med en mer effektiv iterativ lösning.

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;
    }
};

Eller så föredrar du en mer okomplicerad rekursiv 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);
    }
};

Notera: Rekursiven kommer att ge TIME LIMIT EXCEEDED på test 44. Det beror på att den rekursiva funktionen vanligtvis beräknar mellanvärden många många gånger. Till exempel , .  beräknas två gånger.