文章目录
10.1 斐波那契数列
题目链接
题目描述
求斐波那契数列的第 n 项，n <= 39。
解题思路
如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。
递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。
package 斐波那契数列;/*
作者 :XiangLin
创建时间 :26/02/2020 20:44
文件 :Fibona.java
IDE :IntelliJ IDEA
*/
public class Fibona {
public 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];
}
public static void main(String[] args) {
Fibona f = new Fibona();
int a = f.Fibonacci(5);
System.out.println(a);
}
}
考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。
package 斐波那契数列;/*
作者 :XiangLin
创建时间 :26/02/2020 21:15
文件 :Fibon.java
IDE :IntelliJ IDEA
*/
public class Fibon {
public int Fibonacci(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) {
Fibon f = new Fibon();
int n = f.Fibonacci(5);
System.out.println(n);
}
}
由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值。
package 斐波那契数列;/*
作者 :XiangLin
创建时间 :26/02/2020 21:21
文件 :Solution.java
IDE :IntelliJ IDEA
*/
public class Solution {
private int[] fib = new int[40];
public Solution(){
fib[1] = 1;
for (int i = 2; i < fib.length; i++){
fib[i] = fib[i - 1] + fib[i - 2];
}
}
public int Fibonacci(int n){
return fib[n];
}
public static void main(String[] args) {
Solution s = new Solution();
int n = s.Fibonacci(5);
System.out.println(n);
}
}
个人微信公众号，专注于学习资源、笔记分享,欢迎关注。我们一起成长，一起学习。一直纯真着，善良着，温情地热爱生活。
Let the year ahead be the one where all your dreams come true.