python泰波那契序列(leetcode)

泰波那契序列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
上一篇:php 网址参数字符串转换成数组和数字转换成网址字符串


下一篇:为什么在BuildHeap中siftdown要优于siftup