題目

假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

• 原題地址

解題

• 每一步只能走1階或2階，因此每一步可拆分為2個分支，f(n)=f(n-1)+f(n-2)

遞歸

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

動態規劃

public static int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    // f(n-1)
    int f1 = 2;
    // f(n-2)
    int f2 = 1;
    for (int i = 3; i <= n; i++) {
        // f(n) = f(n-1) + f(n-2)
        int fn = f1 + f2;
        /**
         * 如果有下一次循環 
         * 此時的f1就是下一次循環中的f(n-2)
         * 此時的fn就是下一次循環中的f(n-1)
         */
        f2 = f1;
        f1 = fn;
    }
    return f1;
}