leetcode 1137. 第 N 个泰波那契数_给你整数 n,请返回第 n 个泰波那契数 tn 的值 泰波那契序列 tn 定义如下: t0 = 0,

1

题目描述

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

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

示例 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。

解题思路

法1

动态规划:

维护一个三位数组分别记录tn-3,tn-2,tn-1的值

利用公式tn=tn-3+tn-2+tn-1tn-3,tn-2,tn-1的值不断向前滚动,从t3开始分别计算出t3,t4...tn的值,

返回tn的值

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func tribonacci(n int) int {
    //记录tn,tn+1,tn+2的值
    t:=[]int{0,1,1}
    //特殊情况
    if  n<3{
        return t[n]
    }
    //一般情况下
    //动态规划
    //记录结果
    r:=0
    for i:=2;i<n;i++{
        r=t[0]+t[1]+t[2]
        t[0]=t[1]
        t[1]=t[2]
        t[2]=r
    }
    return r
}
1

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 81.48% 的用户 通过测试用例： 39 / 39 炫耀一下:

1

1