假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思想：

1. 这个是数学归纳方法，从最简单的开始算起，找到规律
2. 第n阶是n-1阶的走法 + 第n-2阶的走法之和，是一个斐波那契

3. 注意这类题是找到他的循环部分即可，不牵涉AI的算法，除了if else就是loop，抓住这道题的loop循环是关键

   算法：

4. n=1,和n=2 已知，
5. n>=3 时，记住n-1用的步数和n-2用的步数，分别为f1，f2
6. 第n阶的f3就是f1+f2

    /**
     * 递推思想
     */
    private static int climbStairs(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;

        int f1 = 1;
        int f2 = 2;
        int f3 =0;

        //斐波那契的缓存最近三次的结果
        for(int i = 3; i <= n  ; i++ ){
           f3 = f1 + f2;
           f1 = f2;
           f2 = f3;
        } 
        return f3;
    }

leetcode地址:https://leetcode-cn.com/problems/climbing-stairs/