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