斐波那契数列

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

}