1137. 第 N 个泰波那契数

桃扇骨 2022-09-03 14:30 147阅读 0赞

#### 2021-08-08 LeetCode每日一题 ####

链接：[https://leetcode-cn.com/problems/n-th-tribonacci-number/][https_leetcode-cn.com_problems_n-th-tribonacci-number]

标签：**数学、记忆化搜索、动态规划**

> 题目

泰波那契序列 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）题目保证答案范围在\[0, 2 ^ 31 - 1\]，所以使用int存储即可。

（2）和斐波那契数列一样，只不过这里是三个数之和。

> 编码

class Solution { 
        public int tribonacci(int n) { 
            if (n <= 2) { 
                return n == 0 ? 0 : 1;
            }
    
            int t0 = 0, t1 = 1, t2 = 1, res = 0;
            while (n-- >= 3) { 
                res = t0 + t1 + t2;
                t0 = t1;
                t1 = t2;
                t2 = res;
            }
    
            return res;
        }
    }

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_n-th-tribonacci-number]: https://leetcode-cn.com/problems/n-th-tribonacci-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]: /images/20220829/d429175364d84d60afab60009036f20e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-1137. 第 N 个泰波那契数

目录动态规划题目来源 [1137. 第 N 个泰波那契数][1137. _ N] 动态规划动规五部曲： 1.确定dp数组以及下标的

旧城等待，/ 2024年03月24日 14:55/ 0 赞/ 29 阅读

相关第 N 个泰波那契数

1. 题目分析题目链接来自力扣 : [第 N 个泰波那契数][N] ![image.png][] 运用一点小技巧, 当 Tn+3 = Tn + Tn+1 + T

亦凉/ 2024年03月16日 21:09/ 0 赞/ 64 阅读

相关【算法挨揍日记】day17——1137. 第 N 个泰波那契数、面试题 08.01. 三步问题

![759286e2e1c1423393348ccb1879d427.png][] 1137. 第 N 个泰波那契数 [1137. 第 N 个泰波那契数][1137.

柔光的暖阳◎/ 2024年02月21日 11:48/ 0 赞/ 32 阅读

相关 1137. 第 N 个泰波那契数

2021-08-08 LeetCode每日一题链接：[https://leetcode-cn.com/problems/n-th-tribonacci-number/]

桃扇骨/ 2022年09月03日 14:30/ 0 赞/ 148 阅读

相关 leetcode1137第 N 个泰波那契数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

旧城等待，/ 2022年09月03日 14:14/ 0 赞/ 147 阅读

相关 1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n

秒速五厘米/ 2022年08月31日 04:41/ 0 赞/ 139 阅读

相关算法——矩阵快速幂求第N个斐波那契数

Fibonacci <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

「爱情、让人受尽委屈。」/ 2022年06月07日 04:35/ 0 赞/ 162 阅读

相关第N个斐波那契数对10007取余的结果

问题描述： Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大，现在我们想知

本是古典何须时尚/ 2022年05月17日 01:05/ 0 赞/ 173 阅读

相关【C语言】输出第n个斐波那契数

循环实现 define _CRT_SECURE_NO_WARNINGS include<stdio.h> include<stdlib.h>

青旅半醒/ 2022年02月19日 01:21/ 0 赞/ 300 阅读

相关从零开始算法之路 ---- 第 N 个泰波那契数（LeetCode 第 147 场周赛）

题源: 力扣(LeetCode） [https://leetcode-cn.com/contest/weekly-contest-147/problems/n-th-tribo

太过爱你忘了你带给我的痛/ 2021年11月16日 13:58/ 0 赞/ 246 阅读