題目 1：求斐波那契數(shù)列的第 n 項
代碼實現(xiàn)：
public class Fibonacci {
/**
* 解法 1：遞歸
*
* 優(yōu)點：代碼簡潔
* 缺點：效率不高
*
* @param n
* @return
*/
private static int fibonacci(int n) {
if (n <= 1)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}
/**
* 解法 2：將遞歸的算法用循環(huán)實現(xiàn) (自下而上計算, 根據(jù)f(0)、f(1)算出f(2)...)
*
* 優(yōu)點：提高了時間效率
*
* 時間復(fù)雜度：O(n)
*
* @param n
* @return
*/
private static int fibonacci2(int n) {
if (n <= 1)
return n;
int pre2 = 0, pre1 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre2 + pre1;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
public static void main(String[] args) {
System.out.print("輸入要求斐波那契數(shù)列的項數(shù)：");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int result1 = fibonacci(n);
System.out.print("遞歸的方式：" + result1);
System.out.println();
int result2 = fibonacci2(n);
System.out.print("以循環(huán)的方式實現(xiàn)遞歸：" + result2);
}
}
兩種解法的比較：
遞歸：
優(yōu)點：代碼簡潔
缺點：
- 但由于遞歸是調(diào)用函數(shù)自身村视，而函數(shù)調(diào)用是有時間和空間的消耗的：每一次函數(shù)調(diào)用童谒，都需要在內(nèi)存棧中分配空間以保存參數(shù)奠衔、返回地址及臨時變量，而且往棧里壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時間；
-
調(diào)用棧溢出晾腔。每一次函數(shù)調(diào)用時都需要在內(nèi)存棧中分配內(nèi)存空間愉老，而每個內(nèi)存棧的容量有限场绿，所以，當(dāng)遞歸調(diào)用的層級太多時嫉入，就會超出棧的容量焰盗，導(dǎo)致調(diào)用棧溢出。
循環(huán)的方式實現(xiàn)遞歸：
優(yōu)點：提高了時間效率咒林。自下向上計算每一項的值熬拒，先根據(jù) f(0)、f(1) 計算 f(2) 的值垫竞，再根據(jù) f(1) 澎粟、f(2) 計算 f(3)的值...以此類推就可以求得第 n 項的值了。時間復(fù)雜度為 O(n)
題目 2 ：青蛙跳臺階問題
一只青蛙一次可以跳上 1 級臺階件甥，也可以跳上 2 級臺階捌议。求該青蛙跳上一個 n 級臺階總共有多少種解法。
分析：
- 當(dāng) n 為 1 時引有，只有 1 種跳法瓣颅；
- 當(dāng) n 為 2 時，有 2 種跳法譬正；
- 當(dāng) n > 2 時宫补，f(n) = f(n - 1) + f(n - 2)
代碼實現(xiàn)：
/**
* 青蛙跳臺階問題
* @param n
* @return
*/
private static long jumpFloor(int n) {
if (n <= 2) {
return n;
}
long pre2 = 1;
long pre1 = 2;
long result = 1;
for (int i = 2;i < n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
題目 3 ：青蛙跳臺階問題升級版
一只青蛙一次可以跳上 1 級臺階檬姥，也可以跳上 2 級臺階...也可以跳上 n 級臺階，此時該青蛙跳上 n 級臺階總共有多少種跳法粉怕？
思路：f ( n ) 為 n 級臺階時青蛙的跳法
f ( 1 ) = 1
f ( 2 ) = f ( 2- 1 ) + f ( 2 - 2 )
f ( 3 ) = f ( 3 - 1 ) + f ( 3 - 2 ) + f ( 3 - 3 )
...
f ( n ) = f ( n - 1 ) + f ( n - 2 ) + f ( n - 3 ) + ... + f ( n - n ) = f ( 0 ) + f ( 1 ) + ... + f ( n - 2 ) + f ( n - 1 )
= 2 ^ 1 * f ( n -1 ) = 2 ^ 2 * f ( n - 2 ) = ... = 2 ^ ( n -1 ) * f ( 1 ) = 2 ^ ( n -1 )
代碼實現(xiàn)：
/**
* 青蛙跳臺階問題升級版 f(n) = 2 ^(n - 1)
* @param n
* @return
*/
private static long jumpFloorUpgrade(int n) {
long[] solutions = new long[n];
Arrays.fill(solutions, 1); // 初始化 solutions
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
solutions[i] += solutions[j];
}
System.out.print(solutions[i] + " ");
}
return solutions[n - 1];
}
/**
* f(n) = 2 * f(n - 1)
* @param n
* @return
*/
private static long jumpFloorUpgrade1(int n) {
if (n <= 1) {
return n;
}
return 2 * jumpFloorUpgrade1(n - 1);
}
題目 4 ：矩形覆蓋問題 (類似青蛙跳臺階問題)
用 2 x 1 的小矩形橫著或豎著去覆蓋更大的矩形健民。比如說，用 8 個 2 x 1 的小矩形無重疊的覆蓋一個 2 x 8 的大矩形贫贝，總共有多少種方法秉犹？
思路：小矩形橫著放在大矩形中占 2 列，豎著放 占 1 列稚晚，所以自然而然就歸結(jié)為斐波那契數(shù)列問題了
代碼實現(xiàn)：
private static long coverRectangle(int n) {
if (n <= 2) {
return n;
}
long pre2 = 1;
long pre1 = 2;
long result = 1;
for (int i = 3;i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
