backtracking

Question 1

Tribonacci Number
Top Down intuition

Answer 1

1. Create a hash map dp to store the value of computed tribonacci numbers, initialized with the base cases dp[0] = 0, dp[1] = 1, dp[2] = 1.
2. Let dfs(i) be the value of ith
   tribonacci numbers:

• If i is in dp, return dp[i].
• Otherwise, recursively solve answer = dfs(i - 1) + dfs(i - 2) + dfs(i - 3) and set dp[i] = answer. Then return answer.

3. Return dfs(n).

Question 2

Tribonnaci Top Down Aproach
Code

Answer 2

def tribonacci(n: int) -> int:
    dp = {0: 0, 1: 1, 2: 1}
    def dfs(i):
        if i in dp:
            return dp[i]
        dp[i] = dfs(i - 1) + dfs(i - 2) + dfs(i - 3)
        return dp[i]
    
    return dfs(n)