C++速通LeetCode简单第17题-爬楼梯

思路要点：将问题转化为求斐波那契数列的第n项，然后迭代。

思路分析：最后一次爬的阶数不是1就是2，假设爬n阶的方法数是f(n)，假设最后一次爬1阶，那么爬前面的 n-1阶的方法数是f(n-1)；假设最后一次爬2阶，那么爬前面n-1阶的方法数是f(n-2)。所以可以得到：f(n) = f(n-1) + f(n-2)，也就是斐波那契数列，只是f(1) = 1，f(2) = 2。这样递推下去f(3) = 3， f(4) = 5......

class Solution {
public:
    int p = 1;
    int q = 2;
    int r = 0;
    int climbStairs(int n) {
        if(n == 1) r = p;
        if(n == 2) r = q;
        else
        {
            for(int i = 0;i < n-2;i++)
            {
                r = p + q;
                p = q;
                q = r;
            }
        }
        return r;
    }
};