上台阶问题

1. 楼梯有100阶台阶,上楼时可以一步上1阶,也可以一步上2阶,问共有多少种走法
   解析：
   我们现在想象自己已经站在第n级台阶上了，那么我们上一个位置只能在第n-1或者n-2级台阶上。比如我们在第3级台阶上，我们上一个位置就在第1或者第2级台阶上。也就是说我们到达第3级台阶有两种情况，分别计算着两种情况并相加即可，即到达第1级台阶的方式数加上到达第2级台阶的方式数，结果等于3。同理到达第n级台阶的放法数就等于到达第n-1级台阶与到达第n-2级台阶数之和。这就是一个递归的过程

   
   image.png

用递归：

    public static int getCount(int step){
        if (step==1){
            return 1;
        }
        if (step==2){
            return 2;
        }
        return getCount(step-1)+getCount(step-2);
    } 

用循环

public static int getCount2(int step){
        int pre1=1,pre2=2,result=0;
        if (step==1){
            return pre1;
        }
        if (step==2){
            return pre2;
        }
        for (int i=3;i<=step;++i){
            result=pre1+pre2;
            pre1=pre2;
            pre2=result;
        }
        return result;
    }

另外比较下二者的效率（纳秒）

阶梯数	10	20	30
值	89	10946	1346269
迭代耗时	85416	249843	26615000
循环耗时	4896	4687	7239

2. 楼梯有100阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶,问共有多少种走法

            /          1                    n=1
          /
        /              2                    n=2
f(n)=
        \              4                    n=3
          \
            \ f(n-1)+f(n-2)+f(n-3)          n>=4

用递归：

    public static int getCount(int step){
        if (step==1){
            return 1;
        }
        if (step==2){
            return 2;
        }
        if (step==3){
            return 4;
        }
        return getCount(step-1)+getCount(step-2)+getCount((step-3));
    }

用循环：

 public static int getCount2(int step){
        int pre1=1,pre2=2,pre3=4,result=0;
        if (step==1){
            return pre1;
        }
        if (step==2){
            return pre2;
        }
        if (step==3){
            return pre3;
        }
        for (int i=4;i<=step;++i){
            result=pre1+pre2+pre3;
            pre1=pre2;
            pre2=pre3;
            pre3=result;
        }
        return result;
    }

阶梯数	10	20	30
值	274	121415	53798080
迭代耗时	126666	431823	219137552
循环耗时	4636	2865	4427