泰波那契序列Tn定义如下:
t0 = 0, t1 = 1, t2 = 1, 且在n >= 0 的条件下tn+3 = tn + tn+1 + tn+2
给你整数n,请返回第n个泰波那契数tn 的值
当前项等于前三项之和
解法一 暴力递归
代码如下:
class Solution: def tribonacci(self, n: int) -> int: if n == 0: return 0 if n == 1 or n == 2: return 1 return self.tribonacci(n - 3) + self.tribonacci(n - 2) + self.tribonacci(n - 1)
解法二 动态规划,其实就是对递归结果进行缓存,减少重复计算。
代码如下:
class Solution: def tribonacci(self, n: int) -> int: dp = {i:0 for i in range(n+1)} dp[1] = dp[2] =1 if n <=2: return dp[n] for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] return dp[n]
解法三 压缩空间,使用三个变量
class Solution03: def tribonacci(self, n): a,b,c = 0,1,1 for i in range(n): a,b,c = b,c,a+b+c return a