Java教程

1137.第n个泰波那契数

本文主要是介绍1137.第n个泰波那契数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

泰波那契序列 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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution:
    @functools.lru_cache()  
#在 python3 中,可以使用语言自带的「记忆化搜索」的注解:@functools.lru_cache(),
#它的用法只有一行,即在要执行记忆化的函数上面加上一行注解,即可在语言级别的自动化的记忆化递归。
#1.注意是在python3中使用,2.不加此语句会报超时
    def tribonacci(self, n: int) -> int:
        if n<2:
            return n
        if n==2:
            return 1
        return self.tribonacci(n-1)+self.tribonacci(n-2)+self.tribonacci(n-3)
class Solution(object):
    def tribonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        T=[0]*100
        T[0]=0
        T[1]=1
        T[2]=1
        for i in range(3,n+1):
            T[i]=T[i-1]+T[i-2]+T[i-3]
        return T[n]

 

这篇关于1137.第n个泰波那契数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!