Study note: [Easy] Leetcode #1137 N-th Tribonacci Number
In this article, we will introduce one basic online judge topic, which is recursion.
[1]This problem set #1137 is a kind of variation of popular Fibonacci number.
The subtle change is the recurrence terms and initial condition.
For Fibonacci number, recurrence expression is F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1 as initial condition.
When it comes to Tribonacci number, recurrence expression is T(n) = T(n-1) + T(n-2) + T(n-3) with T(0) = 0, T(1) = 1 as well as T(2) = 1 as initial condition.
Let’s look at the problem description as below.
The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
Example 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4Example 2:
Input: n = 25
Output: 1389537Constraints:
0 <= n <= 37- The answer is guaranteed to fit within a 32-bit integer, ie.
answer <= 2^31 - 1.
The iterative implementation[2] is quite straight-forward, the procedure can be abstracted in two steps.
#1. Setup initial condition (also known as base case).
#2. Write a loops to compute the T(n) with recurrence expression.
For more implementation detail, please refer to the code snippet as below.
Time Complexity: O( n )
The overhead in time is the for loop iterating on i, which is of O( n ).
Space Complexity: O( 1 )
The overhead in space is the storage for base case and looping variable, which is of O( 1 )
— — — — — — — — — — — — — — — — — — — — — — — — — —
On the other hand, the recursive implementation[3] with memorization is also clear and simple.
Time Complexity: O( n )
The overhead in time is the depth of recursion, which is of O( n ).
Space Complexity: O( n )
The overhead in space in space is the storage for loop-up dictionary, func_table, which is of O( n )
Reference:
[1] Reverse String in LeetCode
[2] Python implementation to N-th Tribonacci Number_Iterative
[3] Python implementation to N-th Tribonacci Number_Recursive
