付費限定文章

活用DP: 泰伯納西數列的第n項 Leetcode #1137_精選75題

Faris Mohammed on Unsplash

題目敘述

題目會給我們泰伯納西數列的一般項和初始條件，要求我們實現找出第n項的function。
def tribonacci(self, n: int):

泰伯納西數列的一般項: T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

泰伯納西數列的初始條件: T₀ = 0, T₁ = 1, T₂ = 1

題目的原文敘述

測試範例

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

約束條件

Constraints:

• 0 <= n <= 37

n值介於 0 ~ 37 之間。

• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

答案一定在32bit整數的範圍之內。

這題剛好以前錄過教學影片，提供給讀者作為參考。

演算法 DP動態規劃

回憶一下學過的DP解題框架與三大步驟，鞏固知識點！

1. 定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]