LeetCode 训练场：1137. 第 N 个泰波那契数
1. 题目
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
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 思路
减少暴力递归中的重复运算，可以将子问题的答案存放到备忘录，进行下次运算时先从备忘录中查询，如果已经有对应答案，直接取出用就行，这样就可以大大减少运算的时间。
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
利用上述条件，利用动态规划的思想；
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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
