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
3.1.2 实现
代码语言：javascript复制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 实现
代码语言：javascript复制// 用一个哈希表来当备忘录
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 实现
代码语言：javascript复制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;
}
