1137 Tribonacci 數(shù)列

題目鏈接https://leetcode.cn/problems/n-th-tribonacci-number/

題目描述

Tribonacci 數(shù)列是一種類似于斐波那契數(shù)列的數(shù)列，不同之處在于，Tribonacci 數(shù)列中的每一項是前面三項的和。給定整數(shù) n，求出 Tribonacci 數(shù)列的第 n 項。
Tribonacci 數(shù)列的前幾項為：
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 數(shù)，需要遵循如下步驟：

1. 當 n 為 0 時，Tribonacci 數(shù)為 0；當 n 為 1 或 2 時，Tribonacci 數(shù)為 1。
2. 對于 n 大于等于 3 的情況，則可以利用前三項的和來計算第 n 項。

我們采用動態(tài)規(guī)劃的方法，從第 3 項開始，我們可以通過保存前面三項的值來計算當前項。我們使用三個變量 left、middle 和 right 來分別表示前面三項，然后迭代地更新它們的值以計算出第 n 項。

動態(tài)規(guī)劃（Dynamic Programming, DP）是一種算法設(shè)計思想，適用于解決具有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。動態(tài)規(guī)劃通過將問題分解為更小的子問題來求解，同時保存這些子問題的解，以避免重復計算，最終得到問題的最優(yōu)解。

從 i = 3 到 i = n 逐步計算 Tribonacci 數(shù)。每次計算后更新 left、middle 和 right 的值。

時間復雜度：O(n)，只需要計算 n 項。

代碼實現(xià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