Question

编程题，可爱的小明喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次两个台阶，有的时候一次爬三个

Answer 1

问有几种爬法么。。。逆着推，分情况讨论，假设f(n)表示有n个台阶的时候总共有多少种爬法。

1. 如果最后一次爬1个台阶，那么总共有f(n-1)种爬法

2. 如果最后一次爬2个台阶，那么总共有f(n-2)种爬法

3. 如果最后一次爬3个台阶，那么总共有f(n-3)种爬法

没有其他爬法了。

于是就有了递推公式：f(n) = f(n-1) + f(n-2) + f(n-3)。

然后讨论初始值，我们需要三个初始值：

如果只有1个台阶，爬法当然只有一种，所以f(1)=1。

如果只有2个台阶，爬法当然只有两种，所以f(2)=2。

如果只有3个台阶，爬法有：

1. 一个一个爬

2. 爬1个，再爬2个

3. 爬2个，再爬1个

4. 爬3个

所以f(3)=4。

所以这个问题的解就是求递推公式：

f(n) = f(n-1) + f(n-2) + f(n-3); 其中f(1) = 1; f(2) = 2; f(3) = 4;

这个很像斐波那契数列的求法，模仿它可以得到一个循环的求法：

int climbStairs(int n) {
    if (n < 1) { return 0; }
    if (n == 1) { return 1; }
    if (n == 2) { return 2; }
    if (n == 3) { return 4; }
    int f1 = 1, f2 = 2, f3 = 4;
    int result = 0;
    for(int i=4; i<=n; i++) {
        result = f1 + f2 + f3;
        f1 = f2;
        f2 = f3;
        f3 = result;
    }
    return result;
}

Answer 2

问题是什么？