Exercice de codage – Monter des escaliers – Nombres de Fibonacci – C++ – Juge en ligne
Question : Vous montez des escaliers. Il faut n étapes pour arriver au sommet. A chaque fois, vous pouvez faire 1 pas ou 2 pas. Combien de façons distinctes d’arriver au sommet ?
Description du problème: http://oj.leetcode.com/problems/climbing-stairs/
Ce problème peut sembler difficile au premier abord, mais quand vous y réfléchissez une seconde, vous pourriez le trouver si facile. La réponse est les nombres de Fibonacci (voir ici, ici )
Eh bien, les nombres de Fibonacci originaux sont définis comme des séquences :
Pour ce problème, il suffit de modifier un peu :
et parce que pour 1 seule étape, il n’y a qu’1 chemin distinct et pour 2 étapes, on a deux solutions: 1 + 1 ou 2.
Le reste est en série de Fibonacci. Le parce qu’à partir de la position actuelle, nous sommes peut-être des deux positions précédentes, F(n-1) et F(n-2).
Vous pouvez utiliser la récursivité, mais cela peut être résolu par une solution itérative plus efficace.
Ou vous préférez une fonction récursive plus simple :
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
Remarque: La fonction récursive donnera TIME LIMIT EXCEEDED sur le test 44. En effet, la fonction récursive calcule généralement des valeurs intermédiaires plusieurs fois. Par exemple, , . est calculé deux fois.