import java.util.HashMap; import java.util.Map; public class Fibonacci { // F(0)=0, F(1)=1, n>1时,F(n)=F(n-1)+F(n-2)。 public static int fibonacci(int n) { if (n == 0 || n == 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } /** * 缓存执行结果 */ static Map<Integer, Integer> cacheList = new HashMap<>(); static { cacheList.put(0, 0); cacheList.put(1, 1); } public static int fibonacciUseCache(int n) { int r = cacheList.containsKey(n) ? cacheList.get(n) : 0; if (r == 0) { r = fibonacci(n - 1) + fibonacci(n - 2); } cacheList.put(n, r); return r; } /** * 动态规划:从底部开始解决问题,将所有小问题解决掉,然后合并成一个整体解决方案,从而解决掉整个大问题; * 递归:从顶部开始将问题分解,通过解决掉所有分解的小问题来解决整个问题; * * @param n * @return */ public static int fibonacciDynamic(int n) { int current = 0; int next = 1; int temp; for (int i = 0; i < n; i++) { temp = current; current = next; next += temp; } return current; } public static int fibonacciDynamic2(int n) { int a = 1; // n-1 int b = 0; // n-2 for (int i = 0; i < n; i++) { if (i > 1) { int newA = a + b; int newB = a; b = newB; a = newA; } } return a + b; } /** * 尾调用优化 * @param n * @param curr * @param next * @return */ public static int fibonacciWithNext(int n, int curr, int next) { if (n == 0) { return 0; } if(n==1){ return next; } return fibonacciWithNext(n - 1, next, curr + next); } public static void main(String[] args) { System.out.println(fibonacciUseCache(15)); System.out.println(fibonacciDynamic(15)); System.out.println(fibonacciDynamic2(15)); System.out.println(fibonacciWithNext(15, 0, 1)); } }