Question

题目级别：高级工程师【复杂】

台阶问题。楼梯有N阶，上楼可以一步上一阶，也可以一次上二阶… 也可以一步上n阶。

使用递归算法，计算共有多少种不同的走法，下列选项正确的是：( )

备选答案

public static int t(int n) {
    if (n < 1) {
        return -1;
    } else if (n == 1)
        return 1;
    else if (n > 2)
        return 2;
    else
        return t(n - 1) * t(n - 2);
}

public static int t(int n) {
    if (n < 1) {
        return -1;
    } else if (n == 1) 
        return 1;
    else if (n > 2) 
        return 2;
    else 
        return t(n - 1) + t(n - 2);
}

public static int t(int n) {
    if (n < 1) {
        return -1;
    } else if (n == 1) 
        return 1;
    else if (n == 2) 
        return 2;
    else 
        return t(n - 1) * t(n - 2);
}

public static int t(int n) {
    if (n < 1) {
        return -1;
    } else if (n == 1) 
        return 1;
    else 
        if (n == 2) 
            return 2;
        else 
            return t(n - 1) + t(n - 2);
}

解题分析

思路1：假设n阶台阶有f(n)种走法，可以通过递归的方式进行求解。因为一步可以上1阶或者2阶台阶，那如果先上1个台阶则只需求出剩下的n-1个台阶的走法，如果先上2个台阶则只需求出剩下的n-2个台阶的走法，所以求n个台阶的走法变为求n-1和n-2个台阶的走法，则有f(n) = f(n - 1) + f(n - 2)(其中n > 2)。