爬樓梯

今天又碰到爬樓梯的問題~~~

是leetcode的題目，題目如下(直接複製的)：

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

之前也碰過但沒詳細研究為什麼這樣會對!!!

這次就要把整個過程記下來避免忘記~~~

網路上常看到說要爬到n-1步和n-2步加起來~~~

也沒細說為什麼…後來我靈光一閃是這樣的XD

因為我們只能走1步或2步~~~

所以當我們到達第N樓梯的時候~~~最後一步只有兩種可能!!!

踏上N樓梯的最後一步只有兩種狀況 跨一步 和 跨兩步

所以我們只需要知道跨一步有幾種可能和跨兩步有幾種可能，加起來就是答案~~~

因為最後步伐不同所以不會有重複情況!!

然後往回推~~~最後跨一步有幾種可能也是一樣!!

最後跨一步也是由 走一步 和 走兩步 可能和計算出來~~~

同理最後跨兩步也是一樣~~~

用這樣解法逆推到一開始就會得到答案!!

int climbStairs(int n) {
    if( n < 3 )
    {
        return n;
    }

    std::vector<int> nstep(n,0);
    nstep[0] = 1;
    nstep[1] = 2;

    for(int i = 2; i < n; i++)
    {
        nstep[i] = nstep[i - 1] + nstep[i - 2];
    }

    return nstep[n - 1];
}

上面這方法可以將nstep存起來，重複使用!