#1137

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

N-th Tribonacci Number

Compute the N-th Tribonacci number using state transition dynamic programming with careful memoization and iterative updates.

math dynamic programming memoization

Problem Statement

The Tribonacci sequence generalizes the Fibonacci sequence by summing the preceding three numbers instead of two. Starting with T0 = 0, T1 = 1, and T2 = 1, each subsequent number is defined as Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given an integer n, compute the value of Tn efficiently.

Implement a function that takes an integer n and returns the corresponding Tribonacci number. Ensure your solution handles 0 <= n <= 37 and stays within a 32-bit integer, emphasizing state transition dynamic programming to avoid repeated calculations.

Examples

Example 1

Input: n = 4

Output: 4

T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

Example 2

Input: n = 25

Output: 1389537

Example details omitted.

Constraints

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

Solution Approach

Iterative DP Array

Create an array F of length 38, initialize F[0] = 0 and F[1] = F[2] = 1. Iterate from 3 to n, updating F[i] = F[i-1] + F[i-2] + F[i-3]. Return F[n]. This avoids recursion overhead and exploits memoization automatically.

Optimized Constant Space

Instead of storing all Tribonacci numbers, keep only the last three computed values and update them in a rolling manner. This reduces space from O(n) to O(1) while still following the state transition dynamic programming pattern.

Recursive Memoization

Define a recursive function with memoization to compute Tn. Cache results for each index to prevent recomputation. This method demonstrates the memoization aspect of state transition dynamic programming explicitly, though iterative solutions are generally faster.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for both iterative and memoized approaches. Space complexity is O(n) for full DP arrays or O(1) for optimized rolling variables. Memoization avoids exponential recursion time, a key failure mode in naive recursion.

What Interviewers Usually Probe

Check if you can optimize space using only three variables instead of a full array.
Expect discussion on the state transition formula Tn+3 = Tn + Tn+1 + Tn+2.
Clarify handling of edge cases n = 0, 1, or 2 to ensure correct base initialization.

Common Pitfalls or Variants

Common pitfalls

Using naive recursion without memoization leads to exponential time complexity.
Failing to handle the initial base cases correctly can produce off-by-one errors.
Attempting to optimize prematurely without ensuring the DP state transition is correctly implemented.

Follow-up variants

Compute the N-th Fibonacci number using a similar state transition DP approach as a simpler case.
Modify the sequence to sum the previous four numbers and compute the N-th value, testing generalization.
Implement a Tribonacci-like sequence starting with custom initial values, maintaining DP state transitions.

FAQ

What is the best approach for solving N-th Tribonacci Number?

Use state transition dynamic programming with an array or rolling variables to compute each Tn iteratively and efficiently.

Can I solve it recursively without exceeding time limits?

Yes, but only with memoization. Plain recursion causes exponential time complexity and will likely fail for larger n.

What are the base cases for the Tribonacci sequence?

T0 = 0, T1 = 1, and T2 = 1. Correctly initializing these is critical to prevent off-by-one errors in your DP solution.

How much memory does the iterative approach use?

A full DP array uses O(n) space, but rolling three variables reduces space complexity to O(1) without affecting correctness.

Why is this considered state transition dynamic programming?

Because each state Tn is defined as a deterministic function of the previous three states, matching the classic DP pattern.

terminal

Solution

Solution 1: Dynamic Programming

According to the recurrence relation given in the problem, we can use dynamic programming to solve it.

1

2

3

4

5

6

class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c = 0, 1, 1
        for _ in range(n):
            a, b, c = b, c, a + b + c
        return a

Solution 2: Matrix Exponentiation to Accelerate Recurrence

We define $Tib(n)$ as a $1 \times 3$ matrix $\begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix}$, where $T_n$, $T_{n - 1}$ and $T_{n - 2}$ represent the $n$th, $(n - 1)$th and $(n - 2)$th Tribonacci numbers, respectively.

1

2

3

4

5

6

class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c = 0, 1, 1
        for _ in range(n):
            a, b, c = b, c, a + b + c
        return a

Continue Practicing

#964 least operators to express number #913 cat and mouse #1569 number of ways to reorder array to get same bst