【算法】Fibonacci解法总结

小鱼儿 2022-08-09 15:49 39阅读 0赞

我这里说的Fibonacci数列不仅仅是f(n-1) + f(n-2)的情况，也可以是f(n-1) + f(n-2) + … + f(n-k)的情况。但是这里我们用f(n-1) + f(n-2)来进行讨论，简化理解，举一反三。

## 解法一，递归 ##

实现非常简单。

int fibonacci(int i){
        if(i==0){
          return 0;
        }else if(i==1){
          return 1;
        }else {
          return fibonacci(i-1)+fibonacci(i-2);
        }
      }
    }

## 解法二，动态规划 ##

核心代码如下：

long array[]=new long [n+1];
        array[0]=0;
        array[1]=1;
        for(int i=2;i<n+1;i++){
          array[i]=array[i-1]+array[i-2];
        }

这种解法与递归解法相比，具有非常大的性能提升。

## 解法三，动归优化 ##

将空间优化到O(1)：

int fib(int n) {  
        int last, nextToLast, answer = 0;  
        if (n <= 1) {  
            return 1;  
        }  
        last = nextToLast = 1;  
        for (int i = 0; i < n; i++) {  
            //f(n)=f(n-1)+f(n-2)  
            answer = last + nextToLast;  
            //f(n-2)=f(n-1)  
            nextToLast = last;  
            //f(n-1)=f(n)  
            last = answer;  
        }  
        return answer;  
    }

## 解法四，特殊解法 ##

这种解法可以将时间复杂度优化到O(logn)，牛客网的左老师书上讲的非常清楚，这里直接借助过来以供参考：

/*
    下面介绍一种时间复杂度是O(logn)的方法:
    
    对于斐波那契数列1,1,2,3,5,8,13…….有如下定义:
    
    F( n ) = F( n-1 ) + F( n-2 )
    F( 1 ) = 1
    F( 2 ) = 1
    
    矩阵形式：
    
    [ F( n+1 ) ,  F( n ) ] = [ F( n ) , F( n-1 ) ] * Q  其中 [ F( n+1 ) ,  F( n ) ]为行向量，Q = { [ 1, 1 ]; [ 1, 0 ] }为矩阵
    
    则 [ F( n+1 ) , F( n ) ]=[ 1 , 0 ] * Qn , 
    */
    
    struct Matrix    
    {          
           long long m_00, m_01, m_10, m_11;   
    　　 Matrix ( long long m00 = 0,  long long m01 = 0,  long long m10 = 0,   long long m11 = 0 )    
           :m_00( m00 ), m_01( m01 ), m_10( m10 ), m_11( m11 )     
           {    
           }    
    };
    
    
    Matrix MatrixMultiply (  const Matrix & m1, const Matrix & m2    ）    
    {  
    　　long long m00 = m1.m_00 * m2.m_00 + m1.m_01 * m2.m_10;
    　　long long m01 = m1.m_00 * m2.m_01 + m1.m_01 * m2.m_11; 
    　　long long m10 = m1.m_10 * m2.m_00 + m1.m_11 * m2.m_10    
    　　long long m11 = m1.m_10 * m2.m_01 + m1.m_11 * m2.m_11; 
          return Matrix ( m00,  m01,  m10, m11 );    
    }
    
    Matrix MatrixPower( unsigned int n )    
    {    
           assert(n > 0);    
           Matrix m;    
           if( n == 1)    
           {    
                 m = Matrix(1, 1, 1, 0);    
           }    
          else if(n % 2 == 0)    
           {    
                 m = MatrixPower( n / 2 );    
                 m = MatrixMultiply( matrix, matrix );    
           }    
          else if( n % 2 == 1 )    
           {    
                 m = MatrixPower( (n - 1) / 2 );    
                 m = MatrixMultiply( m, m );    
                 m = MatrixMultiply( m, Matrix( 1, 1, 1, 0 ) );    
           }     
          return m;    
    }  
    long long Fibonacci( unsigned int n )
    {
          int result[2] = { 0, 1 };
          if( n < 2 )
                return result[ n ];
    
          Matrix Q = MatrixPower( n - 1 );　　//注意：按定义式应该用[ 1, 0 ]*Q, 或者等价于{ [ 1 , 0 ]; [ 0, 0 ] }*Q, 但是因为显然结果相同，所以略去这一步。
          return Q.m_00;
    }

## 总结 ##

我觉得Fibonacci数列对于理解动态规划也是非常重要，动态规划的本质就是在递归中优化而来的。  
Fibonacci问题还可以用来解**上台阶问题**，**硬币面值组合问题**。