111. 爬楼梯

描述

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例

比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法
返回 3

思路

典型的斐波那契数列题，但容易想错的地方是求的是方案数目，并不是总共走了多少步，所以定义一个数组 f，数组 f 中元素代表从底部走到当前台阶的方案个数，f[n] = f[n - 1] + f[n - 2];

代码

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        int last = 1, lastlast = 1;
        int now = 0;
        for (int i = 2; i <= n; i++) {
            now = last + lastlast;
            lastlast = last;
            last = now;
        }
        return now;
    }
}