LeetCode 训练场：1137. 第 N 个泰波那契数

1. 题目

1137. 第 N 个泰波那契数

2. 描述

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4

输出：4

解释：

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25

输出：1389537

提示：

0 <= n <= 37

答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

3. 实现方法

3.1 方法 1

3.1.1 思路

F(0) = 0, F(1) = 1, F(2) = 1

F(N) = F(N - 1) + F(N - 2) + F(N - 3), 其中 N > 1

利用递归的方法， 把 f ( n ) f(n)f(n) 问题的计算拆分成 f ( n − 1 ) f(n−1)f(n−1) , f ( n − 2 ) f(n−2)f(n−2) 和f ( n − 3 ) f(n-3)f(n−3)三个子问题的计算，并递归，以 f ( 0 ) f(0)f(0) ， f ( 1 ) f(1)f(1)和f ( 2 ) f(2)f(2) 为终止条件，虽然能求出结果，但是最终会超时；

3.1.2 实现

public int tribonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    if(n == 2){
        return 1;
    }
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
}

3.2 方法 2

3.2.1 思路

减少暴力递归中的重复运算，可以将子问题的答案存放到备忘录，进行下次运算时先从备忘录中查询，如果已经有对应答案，直接取出用就行，这样就可以大大减少运算的时间。

通过添加备忘录，将原来的递归树进行了剪枝，大大减少了子问题，此时的子问题个数变成了 n nn，此时的时间复杂度变成了 O ( n ) O(n)O(n)；

3.2.2 实现

// 用一个哈希表来当备忘录
HashMap<Integer, Integer> hashMap = new HashMap<>();
public int tribonacci(int n) {
    // Base Case
    if (n == 0 || n == 1) {
        return n;
    }
    if(n == 2){
        return 1;
    }
    // 如果计算过了，就直接返回对应答案
    if (hashMap.containsKey(n)) {
        return hashMap.get(n);
    } else {
        // 没计算过的进行计算，同时存入备忘录
        int val = tribonacci(n - 2) + tribonacci(n - 1) + tribonacci(n-3);
        hashMap.put(n, val);
        return val;
    }
}

3.3 方法 3

3.3.1 思路

T(0) = 0, T(1) = 1, T(2) = 1

$T_{N+3} =T_N+T_{N+1}+T_{N+2} $, 其中 N > = 0

利用上述条件，利用动态规划的思想；

状态定义： 设 d p dpdp 为一维数组，其中 d p [ i ] dp[i]dp[i] 的值代表泰波那契序列第 i ii 个数字 。

转移方程： d p [ i + 1 ] = d p [ i ] + d p [ i − 1 ] + d p [ i − 2 ] dp[i + 1] = dp[i] + dp[i - 1] + dp[i-2]dp[i+1]=dp[i]+dp[i−1]+dp[i−2]，即对应数列定义 f ( n + 1 ) = f ( n ) + f ( n − 1 ) + f ( n − 2 ) f(n + 1) = f(n) + f(n - 1) +f(n-2)f(n+1)=f(n)+f(n−1)+f(n−2)；

初始状态： d p [ 0 ] = 0 dp[0] = 0dp[0]=0, d p [ 1 ] = 1 dp[1]=1dp[1]=1 ，d p [ 2 ] = 1 dp[2]=1dp[2]=1，即初始化前三个数字；

返回值： d p [ n ] dp[n]dp[n] ，即泰波那契序列的第 n nn 个数字

时间复杂度：此时主要进行循环操作，时间复杂度为 O ( n ) O(n)O(n)；

3.3.2 实现

public int tribonacci(int n) {
    // base case
    if(n == 0 ){
        return 0;
    }
    if(n==1||n==2){
        return 1;
    }
    int prev = 0;
    int midd = 1;
    int curr = 1;
    for(int i =3;i<=n;i++){
        int sum = prev + midd + curr;
        prev = midd;
        midd = curr;
        curr = sum;
    }
    return curr;
}