Leetcode 1137. N-th Tribonacci Number (Python)

Related Topic

Dynamic-Programming.

Description

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.

Sample I/O

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

Note:

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

Methodology

This question solved by Dynamic Programming. It is similar with question 509. Fibonacci Number!

1. Find the base case (Already given)

   1. When N = 0, F(0) = 0
   2. When N = 1, F(1) = 1
   3. When N = 2, F(1) = 1 …. ```

2. Find the pattern (Already given):

   F(N) = F(N - 1) + F(N - 2) + F(N-3)

   The traditional way is using recursion. If so, the BigO is O(3^N), appearently this is bad performance.

   We use dynamic programming to optimaze it to O(n). The basic idea is create a dp list and init all values with a number, apply the base case for the dp list and then update current value (start from index 3) by adding previous three values so the current value become to store the current result.

   The final result will be the last value of the dp list.

Code

def tribonacci(self, n: int) -> int:
        dp = [0,1,1]+[0 for _ in range(3,n+1)]
        for x in range(3,n+1):
            dp[x] = dp[x-1]+dp[x-2]+dp[x-3]
        return dp[n]

BigO

We iterate all dp array, it will cost O(n), each value will add up last two value as result, it will cost (1+3), in total will be O(n+3n) and It is O(n)