题目 1：求斐波那契数列的第 n 项
代码实现：
public class Fibonacci {
/**
* 解法 1：递归
*
* 优点：代码简洁
* 缺点：效率不高
*
* @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：将递归的算法用循环实现 (自下而上计算, 根据f(0)、f(1)算出f(2)...)
*
* 优点：提高了时间效率
*
* 时间复杂度：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("输入要求斐波那契数列的项数：");
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("以循环的方式实现递归：" + result2);
}
}
两种解法的比较：
递归：
优点：代码简洁
缺点：
- 但由于递归是调用函数自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间；
-
调用栈溢出。每一次函数调用时都需要在内存栈中分配内存空间，而每个内存栈的容量有限，所以，当递归调用的层级太多时，就会超出栈的容量，导致调用栈溢出。
循环的方式实现递归：
优点：提高了时间效率。自下向上计算每一项的值，先根据 f(0)、f(1) 计算 f(2) 的值，再根据 f(1) 、f(2) 计算 f(3)的值...以此类推就可以求得第 n 项的值了。时间复杂度为 O(n)
题目 2 ：青蛙跳台阶问题
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级台阶总共有多少种解法。
分析：
- 当 n 为 1 时，只有 1 种跳法；
- 当 n 为 2 时，有 2 种跳法；
- 当 n > 2 时，f(n) = f(n - 1) + f(n - 2)
代码实现：
/**
* 青蛙跳台阶问题
* @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 )
代码实现：
/**
* 青蛙跳台阶问题升级版 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 列，所以自然而然就归结为斐波那契数列问题了
代码实现：
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;
}
