LeetCode-斐波拉契数列

参考文献

• Classic Computer Science Problems in Java

斐波拉契数列

public class Fib2 {
	private static int fib2(int n) {
		if (n < 2) {
			return n;
		}
		return fib2(n - 1) + fib2(n - 2);
	}

	public static void main(String[] args) {
		System.out.println(fib2(5));
		System.out.println(fib2(10));
	}
}

剪枝

public class Fib3 {

	static Map<Integer, Integer> memo = new HashMap<>(Map.of(0, 0, 1, 1));

	private static int fib3(int n) {
		if (!memo.containsKey(n)) {
			// memoization step
			memo.put(n, fib3(n - 1) + fib3(n - 2));
		}
		return memo.get(n);
	}

	public static void main(String[] args) {
		System.out.println(fib3(5));
		System.out.println(fib3(40));
	}
}

非递归方式

private static int fib4(int n) {
     int last = 0, next = 1; // fib(0), fib(1)
     for (int i = 0; i < n; i++) {
         int oldLast = last;
         last = next;
         next = oldLast + next;
     }
     return last;
 }

 public static void main(String[] args) {
     System.out.println(fib4(5));
     System.out.println(fib4(20));
 }