Description
Tribonacci 數列定義為
T0 = 0, T1 = 1, T2 = 1，Tn = Tn-1 + Tn-2 + Tn-3（n >= 3）。給定n，回傳Tn。
Example:
Input: n = 25 Output: 1389537
Intuition#
費氏數列的三項版本 — 只依賴前三個狀態，用三個變數滾動即可。
- 和 Climbing Stairs 類似，但依賴前三項而非前兩項
T[n] = T[n-1] + T[n-2] + T[n-3]- 只需要三個變數就能算出結果
Approaches#
1: Bottom-Up DP Array#
- 概念: 用陣列存所有值，逐步計算
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun tribonacci(n: Int): Int {
if (n == 0) return 0
if (n <= 2) return 1
val dp = IntArray(n + 1)
dp[0] = 0; dp[1] = 1; dp[2] = 1
for (i in 3..n) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
}
return dp[n]
}
}⭐2: Rolling Variables#
- 概念: 只用三個變數追蹤前三個狀態，空間最優
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun tribonacci(n: Int): Int {
if (n == 0) return 0
if (n <= 2) return 1
var a = 0; var b = 1; var c = 1
for (i in 3..n) {
val next = a + b + c
a = b; b = c; c = next
}
return c
}
}🔑 Takeaways#
- Pattern: 線性遞推 — Fibonacci 的推廣，依賴固定數量的前幾個狀態
- 關鍵技巧: 當狀態轉移只依賴固定個數的前幾個值時，永遠可以用滾動變數把空間降到 O(1)