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);
}