斐波那契数列

斐波拉契数列、青蛙跳台阶

斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

class Solution {
public:
    int fib(int n) {
        //动态规划
        if(n==0) return 0;
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
            dp[i]=dp[i]%1000000007;
        }
        return dp[n];
    }
};

青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

class Solution {
public:
    int numWays(int n) {
        //这个问题就是斐波那契数列，动态规划
        if(n==0) return 1;
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
            dp[i]=dp[i]%1000000007;
        }
        return dp[n];
    }
};

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1 <= n <= 45

class Solution {
public:
    int climbStairs(int n) {
        //斐波那契数列
        if(n==1) return 1;
        vector<int> dp(n+1);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

最长的斐波那契子序列的长度

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

思路：定义状态转移方程为 f(i, j) 表示以 A[i] 结尾前一个数字是 A[j] 的斐波那契数列长度。如果存在一个数字 k，arr[i]=arr[j]+arr[k] (0<=k<j<i) 成立，那么 f(i, j) = f(j, k) + 1。若不存在这样的 k 那么 f(i, j) = 2。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        vector<vector<int>> dp(n, vector<int>(n));
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++){
            mp[arr[i]]=i;
        }
        int res=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                // 存在 k 使得 arr[i] = arr[j] + arr[k] (0 <= k < j < i)
                int temp=arr[i]-arr[j];
                if(mp.count(temp) && mp[temp]<j){
                    dp[i][j]=dp[j][mp[temp]]+1;
                }
                // 不存在 k 使得 arr[i] = arr[j] + arr[k] (0 <= k < j < i)
                else{
                    dp[i][j]=2;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res>2 ? res : 0;
    }
};