1137. 第 N 个泰波那契数

[JalanJiang]

• 原题链接：1137. 第 N 个泰波那契数
• 题解链接：http://jalan.space/leetcode-notebook/#/algorithm/dynamic/?id=_1137-%e7%ac%ac-n-%e4%b8%aa%e6%b3%b0%e6%b3%a2%e9%82%a3%e5%a5%91%e6%95%b0

---

• 输出题解
• 时间复杂度
• 是否最优解

[JalanJiang]

动态规划

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0 for _ in range(38)]
        dp[1] = 1
        dp[2] = 1
        
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        
        return dp[n]

todo：递归

[csming1995]

Java解法：

class Solution {
    public int tribonacci(int n) {
        int[] topThree = new int[]{0, 1, 1};

        if (n < 3) return topThree[n];

        for (int i = 3; i <= n; i++) {
            int temp = topThree[0] + topThree[1] + topThree[2];
            topThree[0] = topThree[1];
            topThree[1] = topThree[2];
            topThree[2] = temp;
        }
        return topThree[2];
    }
}

[JalanJiang]

import functools

class Solution:
    @functools.lru_cache(None)
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 1
        return self.tribonacci(n - 3) + self.tribonacci(n - 2) + self.tribonacci(n - 1)