斐波那契数列

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

斐波那契数列

写一个函数，输入 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];
    }
};

func fib(n int) int {
    //动态规划
    if n == 0 {
        return 0
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for 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];
    }
};

func numWays(n int) int {
    //这个问题就是斐波那契数列，动态规划
    if n == 0 {
        return 1
    }
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1
    for 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];
    }
};

func climbStairs(n int) int {
    //斐波那契数列
    if n == 1 {
        return 1
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for 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;
    }
};

func lenLongestFibSubseq(arr []int) int {
    n := len(arr)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    mp := make(map[int]int)
    for i := 0; i < n; i++ {
        mp[arr[i]] = i
    }
    res := 0
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            // 存在 k 使得 arr[i] = arr[j] + arr[k] (0 <= k < j < i)
            temp := arr[i] - arr[j]
            if k, ok := mp[temp]; ok && k < j {
                dp[i][j] = dp[j][mp[temp]] + 1
            } else {
                // 不存在 k 使得 arr[i] = arr[j] + arr[k] (0 <= k < j < i)
                dp[i][j] = 2
            }
            if dp[i][j] > res {
                res = dp[i][j]
            }
        }
    }
    if res > 2 {
        return res
    }
    return 0
}