【面试题】N级台阶（比如100级），每次可走1步或者2步，求总共有多少种走法？

今天药忘吃喽~ 2022-08-19 05:49 322阅读 0赞

> 走台阶算法（本质上是斐波那契数列）在面试中常会遇到，描述就如题目那样：总共100级台阶（任意级都行），小明每次可选择走1步、2步或者3步，问走完这100级台阶总共有多少种走法？

**一、 题目分析**

这个问题本质上是斐波那契数列，假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-2级台阶，有f(n-2)种跳法。这就表示**f(n)=f(n-1)+f(n-2)**。将上面的斐波那契数列代码稍微改一下就是本题的答案。我们来看一下代码的实现。

**二、斐波那契数列法**

public class Test {
        static final int s = 100; //自定义的台阶数
    
        static int compute(int stair){
            if ( stair <= 0){
                return 0;
            }
            if (stair == 1){
                return 1;
            }
            if (stair == 2){
                return 2;
            }
            return compute(stair-1) + compute(stair-2);
        }
    
        public static void main(String args[]) {
            System.out.println("共有" + compute(s) + "种走法");
        }
    }

**三、 走台阶问题的简单解决算法**

但我自己对于这个题目最早的想法是使用树（多叉树）的方式，100为根节点，每次选择的分支有两种（1、2），然后生成深度为1的树，再从每个2级节点延伸出1、2两个分支，直到所有节点的值<=0，最后统计出所有值为0的叶子节点的数目，就是结果。

不过自己想法实际上把问题复杂化了，下面这种使用递归方式实现的算法本质上和我的思想差不多，但是很明显下面这个算法会简单很多。接下来我们来看看这个算法的实现方式。

public class Test {
        static final int s = 100;  //自定义的台阶数
        static int len = 0, sum = 0;
    
        //最多也只有走100步就到了
        static int step[] = new int[s];
    
        static void compute(final int stair) {
            if (stair < 0)
                return;
    
            //表示已经走完了
            if (stair == 0) {
                printSum();
                sum++;
                return;
            }
    
            //每次到下一步选择时都可以走1-2步
            for (int i = 1; i <= 2; i++) {
                step[len] = i;
                len++;
    
                //进行下一步的迭代，迭代完之后将每后加上的一步去掉，换成其它的步数(如从1换成2)
                compute(stair - i);
                len--;
            }
        }
    
        static void printSum() {
            System.out.print("走法:");
            for (int i = 0; i < len; i++)
                System.out.print(step[i] + " ");
            System.out.println();
        }
    
        public static void main(String args[]) {
            compute(s);
            System.out.println("共有" + sum + "种走法");
        }
    
    }

【参考资料】：  
1、[面试题9:斐波那契数列 - xwdreamer - 博客园][9_ - xwdreamer -]  
2、[PHP上台阶问题（斐波纳契数列应用）][PHP]

[9_ - xwdreamer -]: http://www.cnblogs.com/xwdreamer/archive/2012/05/15/2501606.html
[PHP]: http://blog.csdn.net/zhangchuan5201314/article/details/18410619