Esercizio di codifica – Salire le scale – Numeri di Fibonacci – C++ – Giudice online

Domanda: Stai salendo le scale. Ci vogliono n passi per arrivare in cima. Ogni volta, puoi fare 1 passo o 2 passi. Quanti modi distinti per arrivare in cima?

Descrizione del problema: http://oj.leetcode.com/problems/climbing-stairs/

Questo problema può sembrare difficile all’inizio, ma quando ci pensi per un secondo, potresti trovarlo così facile. La risposta è Numeri di Fibonacci (vedi qui, qui )

Ebbene, i Numeri di Fibonacci originali sono definiti come sequenze:

Per questo problema, dobbiamo solo modificare un po’:

e poiché per 1 solo passaggio, c’è solo 1 modo distinto e per 2 passaggi, abbiamo due soluzioni: 1 + 1 o 2.

Il resto è come la serie di Fibonacci. Il perché dalla posizione attuale, siamo forse dalle due posizioni precedenti, F(n-1) e F(n-2).

Puoi usare la ricorsione, ma questo può essere risolto con una soluzione iterativa più efficace.

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

Oppure preferisci una funzione ricorsiva più semplice:

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

Nota: il ricorsivo produrrà TIME LIMIT EXCEEDED sul test 44. Questo perché la funzione ricorsiva di solito calcola i valori intermedi molte volte. Ad esempio, , .  è calcolato due volte.