题目在这:https://leetcode-cn.com/problems/n-th-tribonacci-number/
法一: (记忆化递归)
思路分析:
本题单纯使用递归方法直接超时。
其实可以看到，当求n的时候，我们需要 三个数， n-1,n-2,n-3 这样就会重复递归很多的数值。
可以使用python3 自带的记忆方法。
完整代码
class Solution:@lru_cachedef tribonacci(self, n: int) -> int:if n == 0:return 0if n == 1 or n == 2:return 1return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)
关于 记忆化函数:
装饰器@lru_cache介绍：这个装饰器实现了备忘的功能，是一项优化技术，把耗时的函数的结果保存起来，避免传入相同的参数时重复计算。lru 是（least recently used）的缩写，即最近最少使用原则。表明缓存不会无限制增长，一段时间不用的缓存条目会被扔掉。
法二: (滚动数组)
思路分析：
实际上解决该问题，我们只需要使用四个变量，使用前三个求出来第四个，然后不断更新前三个的值，继续求第四个。
完整代码:
class Solution:def tribonacci(self, n: int) -> int:a = 0b = 1c = 1if n == 0:return 0if n == 1 or n == 2:return 1for i in range(n-2):res = a + b + ca = bb = cc = resreturn res
法三:(动态规划)
思路分析:
这个没什么好说的，将所有求过的值都放到dp里。一看就懂。
完整代码
class Solution:@lru_cachedef tribonacci(self, n: int) -> int:dp = [0] * 99dp[0] = 0dp[1] = 1dp[2] = 1for i in range(3,n+1):dp[i] = dp[i-1] + dp[i-2] + dp[i-3]return dp[n]
法四:(状态压缩)
思路分析:
这个方法实际上是滚动数组的优化方法，进一步压缩了使用的变量个数，从四个变成了三个。
完整代码:
class Solution:def tribonacci(self, n: int) -> int:a, b, c = 0, 1, 1for i in range(n):a, b, c = b, c, a + b + creturn a