LeetCode 1137. 第 N 个泰波那契数

原题链接

题目描述

泰波那契序列 $T_n$ 定义如下：

$T_0 = 0, T_1 = 1, T_2 = 1$，且在 $n \ge 0$ 的条件下 $Tn+3 = T_n + T_n+1 + T_n+2$。

给你整数 $n$，请返回第 $n$ 个泰波那契数 $T_n$ 的值。

数据范围

$0 <= n <= 37$

答案保证是一个 $32$ 位整数，即 $answer \le 2^{31} - 1$。

样例

输入样例1：

n = 4

输出样例1：

4

样例1解释：

$T_3 = 0 + 1 + 1 = 2$。 $T_4 = 1 + 1 + 2 = 4$。

输入样例2：

n = 25

输出样例2：

1389537

题意

$T_0 = 0, T_1 = 1, T_2 = 1$。求 $T_n (n \geq 0)$， $T_n = T_0 + T_1 + T_2 (n > 2)$。

思路

当 $n \leq 2$​ 的时候，直接返回 $T_n (T_0 = 0, T_1 = 1, T_2 = 1)$，当 $n > 2$​ 的时候，开4个变量，滚动求解就好。

代码

C++

class Solution {
public:
    int tribonacci(int n) {
        if ( n <= 2 ) return n == 0 ? 0 : 1;
        int a = 0, b = 1, c = 1, d;
        while ( n-- > 2 )
        {
            d = a + b + c;
            a = b, b = c, c = d;
        }
        return d;
    }
};