1.斐波那契數(shù)列問題

題目：求斐波那契數(shù)列的第n項(xiàng)

寫一個(gè)函數(shù)，輸入n，求斐波那契(Fibonacci)數(shù)列的第n項(xiàng)
斐波那契數(shù)列的定義如下：
　　　 ┌ 0　　　　　　　,　　n = 0
f(n)=　 ├ 1　　　　　　　,　　n = 1
　　　 └ f(n-1) + f(n-2)　　,　　n > 1

0,1,1,2,3,5,8,13…

思路

函數(shù)本身是遞歸定義，直接用遞歸方式編寫代碼，在遞歸樹中可以得知，這個(gè)過程中出現(xiàn)很多重復(fù)節(jié)點(diǎn)，時(shí)間復(fù)雜度是指數(shù)級(jí)。因此不實(shí)用。
比較好的思路是從底向上計(jì)算f(n)，保留兩個(gè)下層函數(shù)f(n-1) , f(n-2)的值用于下輪計(jì)算。
實(shí)現(xiàn)如下：

public static int Fibonacci(int n) {
    if(n <= 0) 
        return 0;
    if(n == 1) 
        return 1;

    int fibNumOne= 0;
    int fibNumTwo= 1;
    int fib = 0;
    for(int i = 2; i <= n; ++i) {
        fib =  fibNumOne + fibNumTwo;
        fibNumOne= fibNumTwo;
        fibNumTwo= fib;
    }
    return fib;
}

2.跳臺(tái)階問題

題目

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

思路

很明顯的求斐波那契數(shù)列類型的題目
當(dāng)跳n級(jí)臺(tái)階的時(shí)候，設(shè)跳法有f(n)種
青蛙的第一步，可以跳1級(jí)，也可以跳2級(jí)（只有這兩種選擇）

1. 當(dāng)跳1級(jí)的時(shí)候，剩下的有f(n-1)種
2. 當(dāng)跳2級(jí)的時(shí)候，剩下的有f(n-2)種
   因此, f(0) = 0, f(1) = 1, f(2) = 2, f(n) = f(n-1) + f(n-2)

3.變態(tài)跳臺(tái)階問題

題目

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

思路

跳上1級(jí)臺(tái)階有1種跳法（1）
跳上2級(jí)臺(tái)階有2種跳法（1-1、2）
跳上3級(jí)臺(tái)階有4種跳法（1-1-1、1-2、2-1、3）
討論一般情況：假設(shè)跳上n級(jí)臺(tái)階有f(n)種跳法
f(n)種方法包括：
跳上1級(jí)臺(tái)階后直接跳上n級(jí)臺(tái)階 ，此時(shí)有f(1)種跳法
跳上2級(jí)臺(tái)階后直接跳上n級(jí)臺(tái)階 ，此時(shí)有f(2)種跳法
跳上3級(jí)臺(tái)階后直接跳上n級(jí)臺(tái)階 ，此時(shí)有f(3)種跳法
……
跳上n-1級(jí)臺(tái)階后直接跳上n級(jí)臺(tái)階 ,此時(shí)有f(n-1)種跳法
直接跳上n級(jí)臺(tái)階 ，此時(shí)有1種跳法
得到：
當(dāng)n=1時(shí)，f(n) = 1
當(dāng)n>1時(shí)， f(n) = f(1) + f(2) + … + f(n-1) + 1
因此：
f(n) = 2 ^ (n-1)

實(shí)現(xiàn)

public static int JumpFloorII(int target) {
    if(target <= 0) 
        return 0;
    int result = 1;
    for(int i = 0; i < target-1; ++i) {
        result *= 2;
    }
    return result;
}