N-th Tribonacci Number — LeetCode #1137 (Easy)
Tags: Math, Dynamic Programming, Memoization
Related patterns: Dynamic Programming, Memoization, Array
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
The brute force approach involves recursively calculating the Tribonacci numbers. We directly implement the recursive formula, but this leads to repeated calculations, making it inefficient.
The time complexity is O(n²) because each call to the function generates three more calls, leading to an exponential number of calls overall. The space complexity is O(1) since no additional space is used except for the call stack.
- Step 1: Define a recursive function that takes n as input.
- Step 2: Base cases: return 0 if n == 0, return 1 if n == 1 or n == 2.
- Step 3: Recursively return the sum of T(n-1), T(n-2), and T(n-3).
For n = 4:
1. tribonacci(4) calls tribonacci(3), tribonacci(2), tribonacci(1)
2. tribonacci(3) calls tribonacci(2), tribonacci(1), tribonacci(0)
3. tribonacci(2) returns 1, tribonacci(1) returns 1, tribonacci(0) returns 0
4. tribonacci(3) returns 2 (1 + 1 + 0)
5. tribonacci(2) returns 1, tribonacci(1) returns 1
6. tribonacci(4) returns 4 (2 + 1 + 1)
Optimal Solution approach
Time complexity: O(n). Space complexity: O(n).
The optimal solution uses dynamic programming to store previously calculated Tribonacci numbers, avoiding redundant calculations and significantly improving efficiency.
The time complexity is O(n) because we compute each Tribonacci number once. The space complexity is O(n) due to the array storing the results of each computation.
- Step 1: Create an array F of length n+1 to store Tribonacci numbers.
- Step 2: Initialize F[0] = 0, F[1] = 1, F[2] = 1.
- Step 3: Use a loop from 3 to n, setting F[i] = F[i-1] + F[i-2] + F[i-3].
- Step 4: Return F[n].
For n = 4:
1. Initialize F = [0, 1, 1, 0, 0]
2. F[3] = F[2] + F[1] + F[0] = 1 + 1 + 0 = 2 → F = [0, 1, 1, 2, 0]
3. F[4] = F[3] + F[2] + F[1] = 2 + 1 + 1 = 4 → F = [0, 1, 1, 2, 4]
4. Return F[4] = 4
Key Insights
- Dynamic programming can significantly reduce time complexity by storing intermediate results.
- Understanding the recursive relationships helps in formulating the optimal solution.
Common Mistakes
- Not recognizing the need for base cases in recursion.
- Failing to optimize recursive solutions with memoization or dynamic programming.
Interview Tips
- Always consider edge cases, especially for base cases in recursion.
- Explain your thought process clearly when transitioning from brute force to optimal solutions.
- Practice implementing both recursive and iterative solutions to build a strong foundation.
