Day 3 : 1137. N-th Tribonacci Number

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.

Before we get started let's take a deep breath…

It took me some good time to wrap my head around this problem, so let’s take it step by step!

⚠️ ⚠️ ⚠️ The most important thing is that this is not a Fibonacci sequence it is a Tribonacci sequence. ⚠️ ⚠️ ⚠️ 

This is a generalization of the Fibonacci sequence, where each element is the sum of the previous three elements.

This means that for our base case we will need the first three elements!

Alright, let’s break it down together before we dive into the code.

• What are we asked? The nth element of the Tribonacci sequence

• What do we need to calculate each element? Sum of previous 3 elements

• What are our base cases? T0 = 0, T1 = 1, T2 = 1

Let's look at an example with n = 6.

The sequence builds up like this::

1. We start with: [0, 1, 1]

2. T3 = 0 + 1 + 1 = 2

3. T4 = 1 + 1 + 2 = 4

4. T5 = 1 + 2 + 4 = 7

5. T6 = 2 + 4 + 7 = 13

So for n = 6, the answer would be 13!

If we recursively calculate each element by calculating the previous three elements it, we would get the job done 🤙 but suuuuuuper slowly and hit a time limit! But we are getting there!!

We will use dynamic programming to solve this problem. If you need a refresher from the last problem.

Top-Down Approach

There's a very basic template for most top-down recursive approaches!

1. Base case: Define when to stop recursion (at the smallest subproblems)!

2. Memoization: If computation was previously done and stored, just retrieve it!

3. Formula: If computation wasn't done before, compute and save result!

For example, with n = 6: Break down the problems:

• dp[6] = dp[5] + dp[4] + dp[3]

• dp[5] = dp[4] + dp[3] + dp[2]

• dp[4] = dp[3] + dp[2] + dp[1]

• dp[3] = dp[2] + dp[1] + dp[0]

• dp[2] = 1 (base case)

• dp[1] = 1 (base case)

• dp[0] = 0 (base case)

Build the solution back up:

• dp[3] = 1 + 1 + 0 = 2

• dp[4] = 2 + 1 + 1 = 4

• dp[5] = 4 + 2 + 1 = 7

• dp[6] = 7 + 4 + 2 = 13 (answer)

public:
    unordered_map<int, int> dp;
    
    int tribonacci(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        // Check if already calculated
        if (dp.find(n) != dp.end()) 
            return dp[n];
        
        // Calculate and store in memo
        dp[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
        return dp[n];
    }
};

Bottom-Up Approach

The only difference is we will build iteratively from the base cases to bigger problems until we have solved our main problem! So we start by solving our base cases, and up from there!

• dp[0] = 0 (base case)

• dp[1] = 1 (base case)

• dp[2] = 1 (base case)

• dp[3] = 2

• dp[4] = dp[1]+dp[2]+dp[3] = 4

• dp[5] = dp[2]+dp[3]+dp[4] = 7

• dp[6] = dp[3] + dp[4]+ dp[5] = 2+4+7 = 13 (answer)

class Solution {

public:
   int tribonacci(int n) {
       // Handle base cases
       if (n == 0) {
           return 0;
       }
       if (n == 1 || n == 2) {
           return 1;
       }
       
       // Initialize dp vector with size n+1
       vector<int> dp(n + 1, 0);
       
       // Set base cases
       dp[0] = 0;
       dp[1] = dp[2] = 1;
       
       // Calculate tribonacci numbers
       for (int i = 3; i <= n; i++) {
           dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
       }
       
       return dp[n];
   }
};

Resources of the week brought to you by Julia 💗 

• “Venture Deals” by Brad Feld and Jason Mendelson. A great overview of how venture capital funds work and how deals might be structured.

• “#BreakIntoVC” by Bradley Miles. A great guide to breaking into the VC industry.

Self-hacks of the week brought to you by Julia 💗 

I truly believe you can gaslight yourself to success.

1. Follow your heart - Simple, yet so powerful. Like a guide toward what truly matters.

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!