JZ07-斐波那契数列
斐波那契数列
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
class Solution {
//递归，耗资源，需要太多重复计算
public int Fibonacci(int n) {
if (n < 0) {
return -1;
}
if (n <= 1) {
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
//三个变量abc
public int Fibonacci2(int n) {
if (n < 0) {
return -1;
}
if (n <= 1) {
return n;
}
int c = 0;
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
//两个变量abc
public int Fibonacci3(int n) {
int a = 1;
int b = 1;
if (n <= 0)
return 0;
if (n == 1 || n == 2) {
return 1;
}
String[] s = new String[]{"aaa", "bbb"};
while (n > 2) {
b += a; //重新定义b。相当于 c = a + b且 b = c
a = b - a; //重新定义a. 相当于a = b = c - a
n--;
}
return b;
}
//开辟数组dp
public int Fibonacci4(int n) {
if (n < 0) {
return -1;
}
int[] temp = new int[n + 1];
temp[0] = 0;
temp[1] = 1;
for (int i = 2; i <= n; i++) {
temp[i] = temp[i - 1] + temp[i - 2];
}
return temp[n];
}
}