面试算法题:爬楼梯，N级楼梯有多少种走法？

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

By Long Luo

最近去面试时，在一家小公司面试时，公司小BOSS给我出了一道算法题：

一个人爬楼梯，一步可以迈一级，二级，三级台阶，如果楼梯有 \(N\) 级，要求编写程序，求总共有多少种走法。

这个问题应该是一个很老的题目了，用中学数学来说，就是一个排列组合问题。当时拿到这个题目之后，首先想到使用递归的思想去解决这个问题：

N级楼梯问题可以划分为：\(N-1\) 级楼梯，\(N-2\) 级楼梯，\(N-3\) 级楼梯的走法之和。

先计算下0，1，2，3及楼梯有多少种走法：

1
2
3
1 --> 1
2 --> 11 2
3 --> 111 12 21 3

那么，根据以上的分析很容易写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int countNumber(int stepsNum) {
    int sum = 0;

    if (stepsNum == 0) {
        return 0;
    }

    if (stepsNum == 1) {
        return 1;
    } else if (stepsNum == 2) {
        return 2;
    } else if (stepsNum == 3) {
        return 4;
    } else if (stepsNum > 3) {
        return countNumber(stepsNum - 3) + countNumber(stepsNum - 2)
                + countNumber(stepsNum - 1);
    }

    return sum;
}

public static void main(String[] args) {

    for (int i = 0; i <= 10; i++) {
        System.out.println("楼梯台阶数:" + i + ", 走法有:" + countNumber(i));
    }
}

再看看输出：

1
2
3
4
5
6
7
8
9
10
楼梯台阶数:0, 走法有:0
楼梯台阶数:1, 走法有:1
楼梯台阶数:2, 走法有:2
楼梯台阶数:3, 走法有:4
楼梯台阶数:4, 走法有:7
楼梯台阶数:5, 走法有:13
楼梯台阶数:6, 走法有:24
楼梯台阶数:7, 走法有:44
楼梯台阶数:8, 走法有:81
楼梯台阶数:9, 走法有:149

如果求解具体全部走法呢？

仅仅算出有多少种走法是很容易的，如果更近一步呢？基于这个基础，如何输出具体的走法呢？

我们可以使用Stack数据结构和递归的思想去完成这个题目：Stack<T>用于保存每一步的走法。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 一个人爬楼梯，一步可以迈一级，二级，三级台阶，如果楼梯有N级，编写程序，输出所有走法。
 * 
 * @param args
 */
public static void main(String[] args) {
    Stack<Integer> stt = new Stack<Integer>();
    
    buileT(stt, 3);
}

public static void buileT(Stack<Integer> stt, int N) {
    if (N >= 1) {
        stt.push(1);
        buileT(stt, N - 1);
        stt.pop();
    }
    if (N >= 2) {
        stt.push(2);
        buileT(stt, N - 2);
        stt.pop();
    }
    if (N >= 3) {
        stt.push(3);
        buileT(stt, N - 3);
        stt.pop();
    }
    if (N == 0) {
        for (int i : stt) {
            System.out.print("Step:" + i + "-->");
        }
        System.out.println("完成");
    }
}

以上。

———- Updated at 2022.04.21 ———-

这篇文章写于2015年，其实这个题就是 Leetcode 1137. 第 N 个泰波那契数 ，是 70. 爬楼梯 的变体，解决方法可参考 9种求斐波那契数(Fibonacci Numbers)的算法 。

Created by Long Luo at 2015-04-08 00:40:12 @Shenzhen, China. Completed By Long Luo at 2015-04-08 18:15:38 @Shenzhen, China. Updated By Long Luo at 2022年4月21日 14点51分 @Shenzhen, China.