斐波那契数列（Fibonacci sequence）解决方法，面试60分和90分的区别

斐波那契数列（Fibonacci sequence）就是 1，1，2，3，5，8，13，21，34.。。。这个数列大家都很熟悉了。f(n)=f(n-1)+f(n-2). 解决方案，信手拈来，

public static int fib(int n){    	
        if(n==0 ) {
        	return 1;
        }else if(n==1){
        	return 1;        	
        }
        return fib(n-1)+fib(n-2);
    }

这个解决方案，没有错。只是效率太低，因为每次重复计算f(n-1)，如果您在面试中，给出这个解决方案，可以通过，但是只有60分，因为无法在生产线上部署这个解决方案。读者不妨可以试试f(10)和f(25)的计算时间。当计算f(50)时，更是遥遥无期。读者可以自行计算一下计算量。

那么现在介绍一个优化解，就是我计算过了f(a)之后，我把它放在缓存里，这样计算量只有O(n)了。下面给出代码：

public static int fibEnhanced(int n){
    	if(n==0){
    		fibCache.put(0,1);
    		return 1;
    	}else if(n==1){
    		fibCache.put(1,1);
    		return 1;
    	}
    	if(fibCache.keySet().contains(n-2) && fibCache.keySet().contains(n-1)){
    		int sum = fibCache.get(n-2)+fibCache.get(n-1);
    		fibCache.put(n,sum);
    		return sum;
    	}else if(fibCache.keySet().contains(n-2) && (!fibCache.keySet().contains(n-1))){
    		int sum = fibCache.get(n-2)+fibEnhanced(n-1);
    		fibCache.put(n,sum);
    		return sum;     		
    	}else if(!fibCache.keySet().contains(n-2)){
    		int sum = fibEnhanced(n-2)+fibEnhanced(n-1);
    		fibCache.put(n,sum);
    		return sum;     		
    	}
    	return -1;
    }

这样的解决方案，可以得到95分，面试者一般都会很满意了。但是如果你用python写，可以写得非常简洁，答案就留给读者做回家作业了。

60分的方法和95分的方法把它们写在一个文件内，大家可以茶余饭后比较一下：

package org.juhani.fib;

import java.util.HashMap;


public class FibMain{

	private static HashMap fibCache = new HashMap<>();
	
    public static void main(String[] args){
       int n=40;	
    	
       long startNormal = System.nanoTime();	
       int normalAlgorithm = fib(n);
	   System.out.println("sum of normal algorithm is:"+normalAlgorithm);
	   double durationNormal = ((double) (System.nanoTime()-startNormal)) /1000/1000;
	   System.out.println("normal algorithm duration is (milli seconds): "+durationNormal);
	   
	   long startEnhanced = System.nanoTime();	
       int enhancedAlgorithm = fibEnhanced(n);
	   System.out.println("sum of enhanced algorithm is:"+enhancedAlgorithm);
	   double durationEnhanced = ((double) (System.nanoTime()-startEnhanced)) /1000/1000;
	   System.out.println("enhanced algorithm duration is (milli seconds): "+durationEnhanced);
       
	   assert(normalAlgorithm == enhancedAlgorithm);
    }
    
    public static int fib(int n){    	
        if(n==0 ) {
        	return 1;
        }else if(n==1){
        	return 1;        	
        }
        return fib(n-1)+fib(n-2);
    }
    
    
    public static int fibEnhanced(int n){
    	if(n==0){
    		fibCache.put(0,1);
    		return 1;
    	}else if(n==1){
    		fibCache.put(1,1);
    		return 1;
    	}
    	if(fibCache.keySet().contains(n-2) && fibCache.keySet().contains(n-1)){
    		int sum = fibCache.get(n-2)+fibCache.get(n-1);
    		fibCache.put(n,sum);
    		return sum;
    	}else if(fibCache.keySet().contains(n-2) && (!fibCache.keySet().contains(n-1))){
    		int sum = fibCache.get(n-2)+fibEnhanced(n-1);
    		fibCache.put(n,sum);
    		return sum;     		
    	}else if(!fibCache.keySet().contains(n-2)){
    		int sum = fibEnhanced(n-2)+fibEnhanced(n-1);
    		fibCache.put(n,sum);
    		return sum;     		
    	}
    	return -1;
    }
}

写作时间：2022年3月37日周日下午15:20.