Koodausharjoitus – Portaiden kiipeäminen – Fibonacci-numerot – C++ – Online Judge

Kysymys: Kiipeät portaita. Huipulle pääseminen kestää n askelta. Joka kerta voit ottaa 1 tai 2 askelta. Kuinka monta erilaista tapaa päästä huipulle?

Ongelman kuvaus: http://oj.leetcode.com/problems/climbing-stairs/

Tämä ongelma saattaa aluksi näyttää vaikealta, mutta kun ajattelet hetken, saatat löytää sen niin helpoksi. Vastaus on Fibonacci-luvut (katso tästä, täältä )

No, alkuperäiset Fibonacci-luvut määritellään sarjoiksi:

Tätä ongelmaa varten meidän on vain muutettava hieman:

ja koska vain yhdelle vaiheelle on vain yksi erillinen tapa ja kahdelle vaiheelle, meillä on kaksi ratkaisua: 1 + 1 tai 2.

Loput ovat kuin Fibonacci-sarja. Koska nykyisestä sijainnista, olemme mahdollisesti kahdesta edellisestä paikasta, F(n-1) ja F(n-2).

Voit käyttää rekursiota, mutta tämä voidaan ratkaista tehokkaammalla iteratiivisella ratkaisulla.

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

Tai pidät yksinkertaisemmasta rekursiivisesta funktiosta:

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Huomautus: Rekursiivinen antaa  testissä 44 AIKARAJA YLITTYY. Tämä johtuu siitä, että rekursiivinen funktio yleensä laskee väliarvot monta kertaa. Esimerkiksi , .  lasketaan kahdesti.