LeedCode_03-爬楼梯（70）

​
如果n==1，显然只有从0->1一种方法：f(1)=1；
如果n==2，那么有0->1->2、0->2两种方：f(2)=2;
如果n==3,那么可以先爬到第1阶，然后爬两个台阶，
或者先爬到第二阶，然后爬一个台阶，显然f(3)=f(2)+f(1);
以此类推
对于n>=3个台阶,可以先爬到第n-1个台阶，
然后再爬一个台阶，或者先爬到n-2个台阶，然后爬2个台阶，
因此我们可以找出规律：f(n)=f(n-1)+f(n-2)。
​
class Solution {
    private Map<Integer,Integer> store=new HashMap<>();
    public int climbStairs(int n) {
        if (n==1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        if (null!=store.get(n)){
            return store.get(n);
        }
        else{
            int result=climbStairs(n-1)+climbStairs(n-2);
            store.put(n,result);
            return result;
        }
}
}
​