|
| 1 | +>本文首发于公众号「图解面试算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。 |
| 2 | +> |
| 3 | +>个人博客：https://www.zhangxiaoshuai.fun |
| 4 | +
|
| 5 | +**本题选自leetcode中第1137题，easy级别，目前通过率52.4%** |
| 6 | + |
| 7 | +###题目描述： |
| 8 | + |
| 9 | +```txt |
| 10 | +泰波那契序列 Tn 定义如下： |
| 11 | +T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 |
| 12 | +给你整数 n，请返回第 n 个泰波那契数 Tn 的值。 |
| 13 | +
|
| 14 | +示例 1： |
| 15 | +输入：n = 4 |
| 16 | +输出：4 |
| 17 | +解释： |
| 18 | +T_3 = 0 + 1 + 1 = 2 |
| 19 | +T_4 = 1 + 1 + 2 = 4 |
| 20 | +
|
| 21 | +示例 2： |
| 22 | +输入：n = 25 |
| 23 | +输出：1389537 |
| 24 | +
|
| 25 | +提示： |
| 26 | + 0 <= n <= 37 |
| 27 | + 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。 |
| 28 | +``` |
| 29 | + |
| 30 | +###题目分析： |
| 31 | +要是之前有接触过斐波那契数列的话，这道题是非常容易有解决思路的。我们有以下三种方法（正经方法两种，哈哈哈）来解决该问题： |
| 32 | + |
| 33 | +``` |
| 34 | +1.递归（但是leetcode中是无法AC的，超出时间限制，但是还是会将代码展示出来） |
| 35 | +2.动态规划（这种题都是已知前面的来求得未知的，使用dp再合适不过） |
| 36 | +3.暴力（抖机灵，看一乐就可以啦） |
| 37 | +``` |
| 38 | + |
| 39 | +###GIF动画演示： |
| 40 | + |
| 41 | + |
| 42 | + |
| 43 | +##代码： |
| 44 | + |
| 45 | +###递归版本： |
| 46 | + |
| 47 | +```java |
| 48 | +publicint tribonacci(int n) { |
| 49 | +if (n==0) { |
| 50 | +return0; |
| 51 | + } |
| 52 | +if (n==1|| n==2) { |
| 53 | +return1; |
| 54 | + } |
| 55 | +return tribonacci(n-1)+ tribonacci(n-2)+ tribonacci(n-3); |
| 56 | +} |
| 57 | +``` |
| 58 | + |
| 59 | +###动态规划 |
| 60 | + |
| 61 | +```java |
| 62 | +int[] dp=newint[38]; |
| 63 | +publicint tribonacci(int n) { |
| 64 | +if (dp[n]!=0) { |
| 65 | +return dp[n]; |
| 66 | + } |
| 67 | +if (n==0) { |
| 68 | +return0; |
| 69 | + }elseif (n==1|| n==2) { |
| 70 | +return1; |
| 71 | + }else { |
| 72 | +int res= tribonacci(n-1)+ tribonacci(n-2)+ tribonacci(n-3); |
| 73 | + dp[n]= res; |
| 74 | +return res; |
| 75 | + } |
| 76 | +} |
| 77 | +``` |
| 78 | + |
| 79 | +###暴力法（十分暴力，哈哈哈哈……） |
| 80 | + |
| 81 | +```java |
| 82 | +publicint tribonacci(int n) { |
| 83 | +int[]Ts= {0,1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136,5768,10609,19513,35890,66012,121415,223317,410744,755476,1389537,2555757,4700770,8646064,15902591,29249425,53798080,98950096,181997601,334745777,615693474,1132436852,2082876103}; |
| 84 | +returnTs[n]; |
| 85 | +} |
| 86 | +``` |
| 87 | + |