努力刷题的钢铁桂桂卷(๑•̀ㅂ•́)و✧
上学时学到的方法：
1
2
3
4
5
6
public int fib(int n) {
2 if (n == 1 || n == 2) {
3 return 1;
4 }
5 return fib(n - 2) + fib(n - 1);
6 }
数组保存法
1
2
3
4
5
6
7
8
9
public int fib(int n) {
2 int[] fib = new int[n];
3 fib[0] = 1;
4 fib[1] = 1;
5 for (int i = 2; i < n; i++) {
6 fib[i] = fib[i - 2] + fib[i - 1];
7 }
8 return fib[n - 1];
9 }
滚动数组法
1
2
3
4
5
6
7
8
9
10
11
public int fib(int n) {
2 int first = 1;
3 int second = 1;
4 int third = 2;
5 for (int i = 3; i <= n; i++) {
6 third = first + second;
7 first = second;
8 second = third;
9 }
10 return third;
11 }
尾递归法
1
2
3
4
5
6
7
public int fib5(int n, int first, int second) {
2 if (n <= 1) {
3 return first;
4 } else {
5 return fib5(n-1,second,first+second);
6 }
7 }
转载自这里
