Version: Next

上楼梯问题

假设楼梯有n阶台阶，上路可以一步上1阶，也可以一步上2阶，走完n阶台阶共有多少种不同的走法？
假设n阶台阶有f(n)中走法，其中f()是一个根据传入截图数目n返回走法个数的方法，第1步共有2种走法
处理边界情况：当n小到一定程度时，可以方便的求出值
0个台阶：0种走法
1个台阶：一种走法
2个台阶：两种走法
3个台阶：三种走法
一般情况：
第1步有2种走法：
上1阶：还剩下n - 1阶，共f(n - 1)种走法
上2阶：还剩下n - 2阶，共f(n - 2)种走法
所以 f(n) = f(n - 1) + f(n - 2)

/**
 * 上楼梯问题
 */
public class Upstaris {

    /**
     * 传入台阶个数，返回可能的走法数
     *
     * @param n 台阶个数
     * @return 可能的走法数目
     */
    public int f(int n) {
        // n缩小到一定程度，递归退出条件
        if (n <= 3) return n;
        return f(n - 1) + f(n - 2);
    }

    public static void main(String[] args) {
        int res1 = new Upstaris().f(3);

        System.out.println("res1 = " + res1);
    }
}

注意

可以观察到，其递归表达式与斐波那契数列问题一模一样，区别是二者的初始条件不同

因此，其优化思路与斐波那契数列问题一致

/**
 * 优化的方法
 */
public int fPlus(int n) {
    if (n <= 3) return n;

    int first = 2;
    int second = 3;
    int nextSecond = 0;

    for (int i = 4; i <= n; i++) {
        nextSecond = first + second;
        first = second;
        second = nextSecond;
    }

    return nextSecond;
}

上楼梯问题#

注意

上楼梯问题