华为 OD 训练营 · 题解精讲
LC1137. 第 N 个泰波那契数
LC1137. 第 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。
题目解析
1137.gif
参考代码
参考代码
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