Fibonacci Has a Bigger Brother — Tribonacci | LeetCode 1137

You know Fibonacci — add the last two.
Tribonacci adds the last THREE.
Same pattern. One extra term. Completely different feel.

And once you solve this — you will understand
exactly how to extend any DP sequence problem
to any number of previous terms.

Watch till 8:41 for the interview strategy
that gets you from DP array to O(1) space
in under 60 seconds.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CHAPTERS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
0:00 Hook — Fibonacci Has a Bigger Brother
0:37 Problem Statement and Recurrence
1:30 Why Dynamic Programming Fits
2:17 Building the DP Array Solution in C++
3:35 Filling the Array Left to Right
4:51 Fixing Edge Cases and Verifying
6:04 Dry Run — n=4 Traced Step by Step
6:24 Time and Space Complexity
7:16 Space Optimized O(1) Three Variable Solution
8:41 Interview Strategy and Final Validation
10:00 Wrap Up

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPLEXITY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DP Array: Time O(n) | Space O(1) fixed array of 38
Three Variables: Time O(n) | Space O(1) true

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE CORE PATTERN
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Fibonacci: dp[i] = dp[i-1] + dp[i-2]
Tribonacci: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

Base cases:
dp[0] = 0, dp[1] = 1, dp[2] = 1

That is the entire recurrence.
Everything else fills itself automatically.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
O(1) SPACE TRICK
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Keep only three variables a, b, c.
At each step:
next = a + b + c
a = b
b = c
c = next

After the loop c holds t(n).
No array needed. No extra memory.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INTERVIEW STRATEGY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1 → Present DP array solution first
Shows the recurrence clearly
Explains base cases explicitly

STEP 2 → When asked to optimize
Explain only last 3 values matter
Show three-variable O(1) solution

This is the exact two-step progression
interviewers at FAANG expect to see.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DP ROADMAP
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1 → LC 70 - Climbing Stairs
Step 2 → LC 509 - Fibonacci Number
Step 3 → LC 1137 - Tribonacci (this video)
Step 4 → LC 198 - House Robber
Step 5 → LC 322 - Coin Change
Boss → LC 300 - Longest Increasing Subsequence

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
WATCH THESE NEXT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
→ Climbing Stairs — LC 70
→ Binary Search — LC 704
→ Search Insert Position — LC 35
→ Divide Two Integers — LC 29
→ Difference of Element and Digit Sum — LC 2535

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CONNECT WITH ME
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Portfolio → https://rachit-hk-portfolio.vercel.app
GitHub → https://github.com/Rachit-Kakkad1
LeetCode → https://leetcode.com/u/kUyAWXHOC5
LinkedIn → https://linkedin.com/in/rachit-kakkad

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SUBSCRIBE + LIKE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Dropping DSA and Competitive Programming videos every day.
If this helped — like the video.
It takes 1 second and helps this channel
reach more people who need it.
Comment below which DP problem you want next.

#leetcode #tribonacci #leetcode1137 #dynamicprogramming
#dsa #cpp #competitiveprogramming #rachitKakkad
#fibonacci #dp #dpforbeginners #dsaroadmap
#faangprep #googleinterview #codinginterview
#neetcode #striver #dsaforplacements #1ddp

Видео Fibonacci Has a Bigger Brother — Tribonacci | LeetCode 1137 канала Rachit Kakkad