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#
- Memoization (Top-Down DP) — O(n) / O(n)
- 概念: 直接照定義遞迴
T(n) = T(n-1) + T(n-2) + T(n-3)，加 memo 避免重算 - 時間複雜度:
O(n)- 每個狀態只算一次 - 空間複雜度:
O(n)- memo 陣列 + 遞迴堆疊
class Solution {
fun tribonacci(n: Int): Int {
val memo = IntArray(n + 1) { -1 }
fun dp(i: Int): Int {
if (i == 0) return 0
if (i <= 2) return 1
if (memo[i] != -1) return memo[i]
memo[i] = dp(i - 1) + dp(i - 2) + dp(i - 3)
return memo[i]
}
return dp(n)
}
}- Bottom-Up DP Array — O(n) / O(n)
- 概念: 用陣列存所有值，逐步計算
- 時間複雜度:
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]
}
}⭐ 3. Rolling Variables — O(n) / O(1)
- 概念: 只用三個變數追蹤前三個狀態，空間最優
- 時間複雜度:
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)