LeetCode 1137、第 N 个泰波那契数

泰波那契序列 T(n) 定义如下：

T(0) = 0, T(1) = 1, T(2) = 1, 且在 n >= 0 的条件下 T(n+3) = T(n) + T(n+1) + T(n+2)

给你整数 n，请返回第 n 个泰波那契数 T(n )的值。

示例 1：

输入： n = 4 输出： 4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

示例 2：

输入： n = 25 输出： 1389537

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

二、题目解析

三、参考代码

Python

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        
        p = 0
        q = r = 1
        for i in range(3, n + 1):
            s = p + q + r
            p, q, r = q, r, s
        return s

Java

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        
        int p = 0, q = 1, r = 1;
        int s = 0;
        
        for (int i = 3; i <= n; i++) {
            s = p + q + r;
            p = q;
            q = r;
            r = s;
        }
        
        return s;
    }
}

C++

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        
        int p = 0, q = 1, r = 1;
        int s = 0;
        
        for (int i = 3; i <= n; i++) {
            s = p + q + r;
            p = q;
            q = r;
            r = s;
        }
        
        return s;
    }
};