LeetCode刷题——泰波那契数列

泰波那契数列：n=0，T(0)=0  n=1,T(1)=1  n=2,T(2)=1 

                        n>=3时，T(n) =T(n-1)+T(n-2)+T(n-3)

解题思路

n>2时，设了a0,a1,a2=0,1,1

假设n=3,则t_3 = a0+a1+a2 其实也就是前三项和

如何再将a1赋值给a0,a2赋值给a1,前三项和赋值给a2（ao=a1,a1=a2,a2=t_3）

循环次数就是

假设

        n=3 n-2=1

        n=4 n-2=2

        n=5 n-2=3

 

class Solution:
    def tribonacci(self, n):
        if n == 0:
            return 0
        if n <= 2:
            return 1
        
        a0, a1, a2 = 0, 1, 1
        for i in range(n -2):
            num = a0 + a1 + a2
            a0 = a1
            a1 = a2
            a2 = num
        return num

n>=3时，本来想用递归解决的，但是超过了python的最大递归深度

递归代码如下

import sys
sys.setrecursionlimit(1000)


class Solution:
    def tribo_nacci(self, n):
        if n == 0:
            return 0
        elif n <= 2:
            return 1
        else:
            return self.tribo_nacci(n - 1) + self.tribo_nacci(n - 2) + self.tribo_nacci(n - 3)


s = Solution()

但是非常不建议用递归来写，因为他真的非常消耗cpu资源