leetcode:1137 Tribonacci 数列

1137 Tribonacci 数列

题目链接https://leetcode.cn/problems/n-th-tribonacci-number/

题目描述

Tribonacci 数列是一种类似于斐波那契数列的数列，不同之处在于，Tribonacci 数列中的每一项是前面三项的和。给定整数 n，求出 Tribonacci 数列的第 n 项。
Tribonacci 数列的前几项为：
T(0) = 0
T(1) = 1
T(2) = 1
T(3) = T(0) + T(1) + T(2) = 0 + 1 + 1 = 2
T(4) = T(1) + T(2) + T(3) = 1 + 1 + 2 = 4
依此类推…

题目解法

要计算第 n 项的 Tribonacci 数，需要遵循如下步骤：

1. 当 n 为 0 时，Tribonacci 数为 0；当 n 为 1 或 2 时，Tribonacci 数为 1。
2. 对于 n 大于等于 3 的情况，则可以利用前三项的和来计算第 n 项。

我们采用动态规划的方法，从第 3 项开始，我们可以通过保存前面三项的值来计算当前项。我们使用三个变量 left、middle 和 right 来分别表示前面三项，然后迭代地更新它们的值以计算出第 n 项。

动态规划（Dynamic Programming, DP）是一种算法设计思想，适用于解决具有重叠子问题和最优子结构性质的问题。动态规划通过将问题分解为更小的子问题来求解，同时保存这些子问题的解，以避免重复计算，最终得到问题的最优解。

从 i = 3 到 i = n 逐步计算 Tribonacci 数。每次计算后更新 left、middle 和 right 的值。

时间复杂度：O(n)，只需要计算 n 项。

代码实现

C++版本：

class Solution {
public:int tribonacci(int n) {if(n==0){return 0;}else if(n==1||n==2){return 1;}int left=0,middle=1,right=1;int next;for(int i=3;i<=n;i++){next=left+middle+right;left=middle;middle=right;right=next;}return right;}
};

GO版本：

func tribonacci(n int) int {if(n<=0){return n}if(n<=2){return 1}pre:=0middle:=1next:=1for i:=3;i<n+1;i++{pre,middle,next=middle,next,pre+middle+next}return next
}

python版本：

class Solution(object):def tribonacci(self, n):""":type n: int:rtype: int"""if n==0:return 0if n<=2:return 1left,middle,right=0,1,1for i in range(3,n+1):left,middle,right=middle,right,left+middle+rightreturn right