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.

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

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.