解题思路

这个我们一开始就知道有两种走法，走一步和两步，所以当在n = 1的时候返回 1，当n = 2返回 2，那么我们就可以靠这两个推出剩下的走法了。举个例子，当n = 3的时候，我们有两种走法，n = 1的时候走两步，n = 2的时候走一步，所以总方法就是f(n - 1) + f(n - 2)，眼熟的应该就一眼能看出这是什么了，我就不多说了。我们先上一段直接模拟的代码，然后再上最简单的代码。

代码1

class Solution {
public:

    int climbStairs(int n) {
        int ways[1005] = {0};
        ways[1] = 1;
        ways[2] = 2;
        if(n <= 2) return n;
        for(int i = 3; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }
        return ways[n];
    }
};

代码2

应该看出来了吧？这就是完完全全的斐波那契数列啊。。

class Solution {
public:

    int climbStairs(int n) {
        int a = 0, b = 0, c = 1;
        for(int i = 0; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }
};