斐波拉契数列解法

╰+攻爆jí腚メ 2024-05-24 02:26 64阅读 0赞

## 1、题目 ##

题目：力扣 70：  
爬楼梯：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？  
注意：给定 n 是一个正整数。

## 2、解法 ##

**第一种：递归法直接求解**  
存在超时问题  
时间复杂度为O(2^n)

class Solution {
        
    public:
        int climbStairs(int n) {
        
            if(n==1 || n==2) return n;
            return climbStairs(n-1)+climbStairs(n-2);
        }
    };

为了避免重复求解，可以通过一个数据结构（比如散列表）来存储已求解的climbStairs(k)。当递归调用到climbStairs(k)时，先检查是否已求解了该值。如果是，则直接从该散列表中取值返回，避免了重复计算。

#include<unordered_map>
    class Solution {
        
    public:
    
        int climbStairs(int n) {
        
            if(n==1 || n==2)return n;
            if(map.count(n)){
        
                return map.find(n)->second;
            }
            int ret = climbStairs(n-1) + climbStairs(n-2);
            map.insert({
        n,ret});
            return ret;
        }
    private:
        unordered_map<int,int> map;
    };

**第二种：使用斐波拉契的通项公式来解决问题，可能产生精度误差。**  
时间复杂度为O(logn)，空间复杂度为O(1)。

F n = ( 1 + 5 2 ) n − ( 1 − 5 2 ) n 5 F\_\{n\}=\\frac\{\\left(\\frac\{1+\\sqrt\{5\}\}\{2\}\\right)^\{n\}-\\left(\\frac\{1-\\sqrt\{5\}\}\{2\}\\right)^\{n\}\}\{\\sqrt\{5\}\} Fn=5(21\+5)n−(21−5)n

#include<math.h>
    class Solution {
        
    public:
        int climbStairs(int n) {
        
            double sqrt_5 = sqrt(5)；
            double sum_n = pow((1+sqrt_5)/2,n+1) - pow((1-sqrt_5)/2,n+1);
            return int((1/sqrt_5)*sum_n);
        }
    };

**第三种：动态规划**  
时间复杂度为O(n)，空间复杂度为O(n)。

class Solution {
        
    public:
        int climbStairs(int n) {
        
            int num[n+1];
            num[0] = 1;
            num[1] = 1;
            for(int i=2;i<=n;++i){
        
                num[i] = num[i-1] + num[i-2];
            }
            return num[n];
        }
    };

优化空间复杂度，采用滚动数组的方式，空间复杂度降为O(1)。  
将递归求解的方式改为非递归的方式，实现如下：

class Solution {
        
    public:
        int climbStairs(int n) {
        
            int p = 0, q = 0, r = 1;
            for (int i = 1; i <= n; ++i) {
        
                p = q; 
                q = r; 
                r = p + q;
            }
            return r;
        }
    };