Skip to content

001 — Fibonacci Number

Source

  • Original source: Classic introductory DP exercise
  • Platform: LeetCode — https://leetcode.com/problems/fibonacci-number/
  • Topic: dynamic programming
  • Difficulty: Easy
  • Pattern: 1D linear DP
  • Basic idea inherited from: plain recursion (folder 06) — fib(n) = fib(n-1) + fib(n-2)

1. Problem in simple words

তোমাকে একটা সংখ্যা n দেওয়া হলো। Fibonacci sequence-এর n-তম সংখ্যাটা বের করো। Sequence-টা শুরু হয় 0, 1 দিয়ে, তারপর প্রতিটা সংখ্যা তার আগের দুটোর যোগফল।

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   for n >= 2

sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

এই problem-টা DP শেখার "hello world" — একই জিনিস তিনভাবে লিখবে: memoization, tabulation, তারপর O(1) space।

2. Which basic idea does this inherit from?

এটা সরাসরি recursion থেকে আসে (folder 06)। F(n) = F(n-1) + F(n-2) — এই recurrence-টা চোখে দেখলেই recursive function লেখা যায়। কিন্তু plain recursion এখানে একই sub-প্রশ্ন বারবার করে, তাই আমরা সেই recursion-টাকেই DP দিয়ে smart বানাই — solved উত্তর আর দ্বিতীয়বার compute করি না।

3. What is the hidden math or logic?

লুকানো logic হলো overlapping subproblems। fib(5) compute করতে গিয়ে fib(3) দুবার, fib(2) তিনবার গোনা হয়। মাত্র n+1-টা distinct উত্তর (F(0) থেকে F(n)) আছে, কিন্তু naive recursion সেগুলো exponential বার গোনে। প্রতিটা distinct উত্তর একবার গুনে রেখে দিলেই কাজটা O(n) হয়ে যায়।

4. Which data structure is needed?

একটা array (size n+1) tabulation-এর জন্য, বা একটা dictionary memoization-এর জন্য। আর O(1) version-এ শুধু দুটো variable — কারণ প্রতিটা cell কেবল আগের দুটো cell পড়ে।

5. Why this data structure fits

DP-র state এখানে একটা মাত্র সংখ্যা: index i। তাই একটা flat array নিখুঁতভাবে state-গুলো ধরে রাখে — dp[i] = F(i)। যেহেতু dp[i] শুধু dp[i-1] আর dp[i-2] পড়ে, পুরো array লাগেই না; দুটো variable-এ চলে যায়। এটাই standard DP space optimization।

6. Real-life analogy

ভাবো তুমি সিঁড়ি বেয়ে উঠছ আর প্রতিটা ধাপে আগের দুই ধাপের সংখ্যা যোগ করছ। যদি প্রতিবার নিচ থেকে আবার গুনতে শুরু করো, পাগল হয়ে যাবে। বুদ্ধিমান লোক শুধু শেষ দুটো ধাপের ফল মনে রাখে, এক ধাপ এগোয়, পুরোনো সবচেয়ে নিচেরটা ভুলে যায়। সেই "শেষ দুটো মনে রাখা"-ই O(1) DP।

7. Visual explanation

Tabulation table কীভাবে বাঁ থেকে ডানে ভরে — n = 8:

index :  0   1   2   3   4   5   6    7    8
dp    :  0   1   ?   ?   ?   ?   ?    ?    ?      <- base cases লেখা

ভরা শুরু:
dp[2] = dp[1] + dp[0] = 1 + 0 = 1
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp[4] = dp[3] + dp[2] = 2 + 1 = 3
dp[5] = dp[4] + dp[3] = 3 + 2 = 5
dp[6] = dp[5] + dp[4] = 5 + 3 = 8
dp[7] = dp[6] + dp[5] = 8 + 5 = 13
dp[8] = dp[7] + dp[6] = 13 + 8 = 21

index :  0   1   2   3   4   5   6    7    8
dp    :  0   1   1   2   3   5   8   13   21    <- answer dp[8] = 21

প্রতিটা arrow শুধু বাঁ দিকের দুটো filled cell-এ তাক করে — তাই বাঁ-থেকে-ডান fill order নিরাপদ।

8. Example input and output

Input : n = 2   -> Output: 1     (F(2) = F(1) + F(0) = 1 + 0)
Input : n = 5   -> Output: 5
Input : n = 10  -> Output: 55

Edge case 1: n = 0 -> Output: 0
Edge case 2: n = 1 -> Output: 1

9. Brute force thinking

প্রথম সরল চিন্তা: recurrence-টাকে হুবহু recursion-এ লিখে ফেলা।

fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

সঠিক, পড়তে সুন্দর — কিন্তু লুকিয়ে ভয়ংকর।

10. Why brute force is slow

এই recursion O(2^n) time নেয়, কারণ একই sub-প্রশ্ন বারবার solve করে। fib(50) মোটামুটি 2^50-টা call করে মাত্র 51-টা distinct উত্তর বের করতে। Call tree-টা বিশাল কিন্তু তার প্রায় পুরোটাই déjà vu — repeated কাজ। এটাই DP দিয়ে ঠিক করার মূল সমস্যা।

11. Key observation

মূল observation: distinct উত্তর মাত্র n+1-টা। তাহলে প্রতিটা উত্তর একবার গুনে কোথাও লিখে রাখলে, দ্বিতীয়বার আর গোনা লাগে না — exponential কাজ এক ধাক্কায় linear হয়ে যায়।

12. Optimized intuition

State (শব্দে): dp[i] = Fibonacci sequence-এর i-তম সংখ্যা, অর্থাৎ F(i)।

Transition:

dp[i] = dp[i-1] + dp[i-2]

Base case: dp[0] = 0, dp[1] = 1।

Answer location: dp[n]।

এই repo-র doctrine "think top-down, ship bottom-up" মেনে — আগে memoization-এ ভাবো (recursion-এর আয়না), তারপর tabulation-এ ship করো, তারপর space কমাও।

Memoization (top-down): সেই recursion-টাই রাখো, সাথে একটা খাতা (dict)। Solve করার আগে খাতা দেখো, পরে লিখে রাখো।

Tabulation (bottom-up): খাতাটা ছোট-থেকে-বড় order-এ একটা loop দিয়ে ভরো, recursion ছাড়াই।

O(1) space: যেহেতু শুধু আগের দুটো মান লাগে, পুরো array না রেখে দুটো variable a, b rolling করো।

13. Thinking tweak

মোচড়: "সংখ্যাটা recurse করে বের করব" ভাবার বদলে ভাবো "ছোট থেকে শুরু করে একটা একটা করে উপরে উঠব, পথে শুধু শেষ দুটো মান হাতে রাখব।" তাহলে exponential recursion মুহূর্তে একটা simple loop হয়ে যায়।

14. Step-by-step dry run

n = 5, O(1) version দিয়ে (a = F(i-1), b = F(i)):

  1. শুরু: a = 0 (F(0)), b = 1 (F(1))
  2. i = 2: a, b = b, a + b → a = 1, b = 1 (F(2) = 1)
  3. i = 3: a, b = 1, 2 (F(3) = 2)
  4. i = 4: a, b = 2, 3 (F(4) = 3)
  5. i = 5: a, b = 3, 5 (F(5) = 5)
  6. loop শেষ। b = 5 = answer

15. Python solution

# ---- way 1: memoization (top-down) ----
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:                 # খাতায় আছে? পড়ে নাও
        return memo[n]
    if n <= 1:                    # base case
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]                # লিখে রাখো, তারপর return

# ---- way 2: tabulation (bottom-up) ----
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)            # খাতাটা array হিসেবে
    dp[0], dp[1] = 0, 1           # base cases আগে লেখা
    for i in range(2, n + 1):     # fill order: small -> large
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]                  # উত্তরের ঠিকানা

# ---- way 3: O(1) space ----
def fib_fast(n):
    if n <= 1:
        return n
    a, b = 0, 1                   # a = F(i-1), b = F(i)
    for _ in range(2, n + 1):
        a, b = b, a + b          # এক ধাপ এগোও, পুরোনোটা ভুলে যাও
    return b

# ---- tests ----
expected = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
for i, want in enumerate(expected):
    assert fib_memo(i) == want, (i, fib_memo(i))
    assert fib_tab(i) == want, (i, fib_tab(i))
    assert fib_fast(i) == want, (i, fib_fast(i))

assert fib_fast(20) == 6765            # বড় n-এ তিনটাই মেলে
assert fib_memo(20) == fib_tab(20) == fib_fast(20)
print("সব test pass!")

16. Line-by-line code explanation

  • fib_memo: memo হলো খাতা; if n in memo আগের উত্তর reuse করে; base case n <= 1; computed মান memo[n]-এ লিখে রাখা হয় return-এর আগে।
  • fib_tab: dp array খাতাটা ধরে; dp[0], dp[1] base cases; loop ছোট-থেকে-বড় ভরে, তাই dp[i-1] ও dp[i-2] সবসময় আগেই filled।
  • fib_fast: a, b শুধু শেষ দুটো মান; a, b = b, a + b এক assignment-এই দুজনকে এক ধাপ এগিয়ে দেয়, পুরো array লাগে না।

17. Output walkthrough

expected list-টা F(0) থেকে F(10) পর্যন্ত সঠিক মান। Loop প্রতিটা i-তে তিনটা function-ই check করে — সব মিললে assert চুপ থাকে। তারপর fib_fast(20) == 6765 আর তিন function-এর সমতা যাচাই হয়। সব pass হলে শেষে print: সব test pass!।

18. Time complexity

  • Memoization: O(n) — প্রতিটা distinct i একবার করে compute হয়।
  • Tabulation: O(n) — একবার loop।
  • O(1)-space version: O(n) — একবার loop।

(Naive recursion ছিল O(2^n) — সেটাই DP fix করল।)

19. Space complexity

  • Memoization: O(n) — dict + recursion stack।
  • Tabulation: O(n) — dp array।
  • Fast version: O(1) — শুধু দুটো variable।

20. Common mistakes

  • Base case ভুল করা — F(0) কে 1 ভাবা; এই সংজ্ঞায় F(0) = 0।
  • Tabulation-এ dp = [0]*(n+1) করার পর n <= 1 case আলাদা না করা — তখন n = 0-এ dp[1] index error দেবে।
  • O(1) version-এ a, b = b, a + b-এর বদলে আলাদা লাইনে a = b তারপর b = a + b লেখা — দ্বিতীয় লাইনে a ততক্ষণে বদলে গেছে, ভুল মান।

21. Which basic problem this inherits from

ভিত্তি: plain recursion (folder 06) — fib(n) = fib(n-1) + fib(n-2)। এই folder-এর ../concept.md-এ ঠিক এই fib দিয়েই memoization আর tabulation introduce করা হয়েছে; ../implementation.py-তে runnable version আছে।

22. Similar harder problems

23. Pattern learned

1D linear DP: state একটা মাত্র index, transition আগের অল্প কয়েকটা cell পড়ে। আর শিখলে memoization → tabulation → O(1) space-এর rolling-variable trick — যা প্রায় সব 1D DP-তে কাজে লাগে।

24. Final summary

ভবিষ্যতের আমাকে: "Fibonacci = সবচেয়ে সহজ DP। State হলো index i, transition dp[i] = dp[i-1] + dp[i-2]।" তিনভাবে লিখতে পারা চাই — recursion+memo (ভাবার জন্য), table (ship করার জন্য), দুই variable (space বাঁচানোর জন্য)। এই rolling trick মাথায় গেঁথে রাখো; পরের প্রায় প্রতিটা 1D DP-তে ফিরে আসবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।