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.
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.