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?1)$ , $f(n?2)$ 和 $f(n-3)$三个子问题的计算，并递归，以 $f(0)$ ， $f(1)$和 $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$，此时的时间复杂度变成了 $O(n)$；

3.2.2 实现

// 用一个哈希表来当备忘录
HashMap<Integer, Integer> hashMap = new HashMap<>();public int tribonacci(int n) {// Base Caseif (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

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

• 状态定义： 设 $dp$ 为一维数组，其中 $dp[i]$ 的值代表泰波那契序列第 $i$ 个数字 。
• 转移方程： $dp[i + 1] = dp[i] + dp[i - 1] + dp[i-2]$，即对应数列定义 $f(n + 1) = f(n) + f(n - 1) +f(n-2)$；
• 初始状态： $dp[0] = 0$, $dp[1]=1$ ， $dp[2]=1$，即初始化前三个数字；
• 返回值： $dp[n]$ ，即泰波那契序列的第 $n$ 个数字
• 时间复杂度：此时主要进行循环操作，时间复杂度为 $O(n)$；

3.3.2 实现

public int tribonacci(int n) {// base caseif(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;
}