LeetCode 1137.泰波那契数列

本文主要是介绍LeetCode 1137.泰波那契数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode-cn.com/problems/n-th-tribonacci-number/
泰波那契序列 Tn 定义如下：

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

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

暴力递归（超时）

var tribonacci = function(n) {if(n === 0) {return 0} else if(n ===1 || n === 2) {return 1} else {return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)}
};

带备忘录的递归解法
递归解法超时在与大量的重复计算，可以使用数组充当备忘录，在计算出子问题答案后先记载在备忘录内，每次遇到子问题就在备忘录里查找答案，如果已经有答案了就直接拿来使用而不是再耗时去计算。

var tribonacci = function(n) {if(n === 0) {return 0} else if(n === 1 || n === 2) {return 1} else {let m = new Array(n + 1).fill(0)if(m[n]) {return m[n]}m[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)return m[n]}
};

动态规划

var tribonacci = function (n) {let dp = new Array(n + 1).fill(0);dp[1] = dp[2] = 1;for (let i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];
};

状态压缩
由状态转移方程可知，当前状态只和前面三个状态有关，所以其实不需要存储所有的状态，只需要存储前面三个状态就可以了，可以把空间复杂度会降到O(1)

var tribonacci = function (n) {if(n === 0) {return 0} else if(n === 1 || n === 2) {return 1} else {let pre1 = 0let pre2 = 1let pre3 = 1let result = 0for(let i = 3; i <= n; i++) {result = pre1 + pre2 + pre3pre1 = pre2pre2 = pre3pre3 = result}return result}
};