offer0007
题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39
思路与代码：
- 方法一：
直接用 循环+数组求
#空间需求大，但优点是保存了每一个n值下的Fibonacci值
public static int Fibonacci(int n) {
if (n <= 0) return 0;
int[] arr = new int[40];
arr[1] = 1;
arr[2] = 1;
if (n > 2) {
for (int i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
}
return arr[n];
}
- 方法二：
动态规划->只需要两个变量来保存状态
[1] [2] [3] [4] [5] [6]
1 1 2 3 5 8
#节省存储空间
public int Fibonacci(int n) {
int f1 = 0;
int f2 = 1;
if (n <= 0) return 0;
if (n == 1 || n == 2) return 1;
n -= 2;
while (n-- >= 0) {
f2 += f1;
f1 = f2 - f1;
}
return f2;
}
- 方法三：
递归求解
#耗时大
public int Fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1 || n == 2) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Offer0008
题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：
通过找规律的方法，可以发现
[1] [2] [3] [4] [5]
1 2 3 5 8
推算这样的规律：f(n)=f(n-1)+f(n-2)
代码：
推出的规律就是斐波那契数列，其他实现参照剑指offer0007
public static int JumpFloor(int target) {
if (target <= 0) return 0;
if (target == 1) return 1;
if (target == 2) return 2;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}