Küsimus: Ronite trepist. Tippu jõudmiseks kulub n sammu. Iga kord saate teha 1 või 2 sammu. Kui palju erinevaid viise tippu jõudmiseks?
Probleemi kirjeldus: http://oj.leetcode.com/problems/climbing-stairs/
See probleem võib esmapilgul tunduda keeruline, kuid kui te hetkeks järele mõtlete, võib see osutuda nii lihtsaks. Vastus on Fibonacci numbrid (vt siit, siit )
Algsed Fibonacci numbrid on määratletud jadadena:
Selle probleemi lahendamiseks peame lihtsalt veidi muutma:
ja 
kuna ainult 1 sammu jaoks on ainult 1 eristatav viis ja 2 sammu jaoks, on meil kaks lahendust: 1 + 1 või 2.
Ülejäänud on nagu Fibonacci seeria. 
Sest praegusest positsioonist oleme tõenäoliselt kahest eelmisest positsioonist, F(n-1) ja F(n-2) .
Võite kasutada rekursiooni, kuid seda saab lahendada tõhusama iteratiivse lahendusega.
Või eelistate lihtsamat rekursiivset funktsiooni:
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};Märkus. Rekursiiv annab testis 44 väärtuse TIME LIMIT EXCEEDED. Seda seetõttu, et rekursiivne funktsioon arvutab tavaliselt vaheväärtusi mitu korda. Näiteks 
, 
. 
arvutatakse kaks korda.