वानर राज की सीढ़ियों का रहस्य
🪷 वानर राजा की सीढ़ियों की पहेली
कदमों, स्मृति और स्पष्टता की कथा — जहाँ एक साधारण सीढ़ी Dynamic Programming का पहला पाठ बन जाती है।
पात्र: वानर राज, अर्जुन, गुरु बोधि · स्तर: शुरुआती · पैटर्न: Dynamic Programming (1D)
🎭 हमारे पात्र
इस कथा में, वानर राज समस्या खड़ी करते हैं, और गुरु बोधि समाधान सिखाते हैं। दोनों अलग-अलग भूमिकाएं निभाते हैं—एक परीक्षा लेता है, दूसरा ज्ञान देता है।
📜 प्रभात सूत्र — परीक्षा का दिन
गुरुकुल में सूर्योदय। सुनहरी रोशनी पत्थर की सीढ़ियों पर फैल गई। सुबह की धुंध धीरे-धीरे उठ रही थी।
आज विशेष दिन था। वानर राज आए थे—वे जो विद्यार्थियों को कठिन पहेलियों से परखते हैं। रटने वाले और सोचने वाले में फर्क करते हैं।
सीढ़ियों के नीचे खड़ा था अर्जुन। युवा, उत्सुक, और पहले से हार चुका।
छाती में जकड़न थी। वही feeling जो हर exam से पहले आती है। कितनी सीढ़ियाँ होंगी? पचास? सौ? पूरी रात वो गिनता रहा—छत को घूरता रहा—और संख्याएं बस... बढ़ती गईं। गुणा होती गईं। कितने तरीकों से असफल हो सकता हूं? उसका दिमाग फुसफुसाया। सभी तरीकों से।
बहुत ऊपर बैठे थे वानर राज। स्थिर। लाठी गोद में। पूंछ आकाश की ओर मुड़ी—एक प्रश्नचिह्न की तरह।
टोक।
लाठी से एक थपकी। पत्थर ने गूंज दी।
चुनौती शुरू हो चुकी थी।
📜 प्रश्न सूत्र — वानर राज की चुनौती
वानर राज ऊपर से देख रहे थे। उन्होंने हज़ारों विद्यार्थियों को ठीक वहीं खड़े देखा था—कंधे झुके, असफलता पहले से गिन रहे।
अर्जुन का पेट ऐसे सिमटा मानो धरती खिसक गई हो। अलग-अलग तरीके? उसका दिमाग घूम गया। "मतलब… 1-1-1-1-1 एक तरीका है, और 2-1-1-1 दूसरा, और 1-2-1-1 तीसरा…" उसे तो ऊपर का छोर भी दिखाई नहीं दे रहा।
शब्द गले में अटक गए। उसने माथे पर हथेली रख दी। एक-एक-एक। एक-दो। दो-एक। एक-एक-दो… संयोजन उसके दिमाग में पटाखों की तरह फूट रहे थे, हर एक और अधिक संभावनाओं में टूट रहा था, और अधिक, और अधिक—
वानर राज की मुस्कान चौड़ी हुई—उपहास नहीं, जानने वाली। किसी ऐसे की मुस्कान जिसने घबराहट का यह पल हज़ार बार पहले देखा हो।
📜 व्याकुलता सूत्र — गुरु बोधि का आगमन
कदमों की आहट। वस्त्रों के पत्थर पर रगड़ने की आवाज़।
गुरु बोधि प्रकट हुए। शांत। वह शांति जो हज़ारों विद्यार्थियों को एक ही समस्या पर घबराते देखने से आती है।
वानर राज समस्या देते हैं, गुरु बोधि समाधान सिखाते हैं—यही परंपरा है। जब विद्यार्थी घबराते हैं, तब गुरु आते हैं।
उसने कनपटी पर हथेलियां रख दीं। "यह ऐसा है मानो—हर सीढ़ी और branches में बंट जाती है। एक-एक-एक-दो-एक, दो-एक-एक, एक-दो-एक-एक—मैं ट्रैक खो देता हूं। भूल जाता हूं कि क्या गिना। फिर से शुरू करता हूं। जैसे एक recursive function को debug कर रहा हूं जिसका base case ही नहीं मिल रहा।"
उसके हाथ कांप रहे थे।
गुरु बोधि फौरन नहीं बोले। खड़े रहे। अर्जुन की घबराहट को शांत होने दिया। फिर धीरे से लाठी पहली सीढ़ी पर रखी।
📜 विवेक सूत्र — DP Pattern की खोज
गुरु बोधि ने अर्जुन के कंधे पर हाथ रखा। "अब मैं तुम्हें सोचने का तरीका सिखाऊंगा, वत्स।"
उन्होंने लाठी से पहली सीढ़ी पर दो निशान खोदे। एक, फिर दूसरा। सरल। साफ़।
Base truths:
dp(0) = 1 # स्थिर खड़े रहना, प्रारंभ
dp(1) = 1 # पहला कदम उठाने का एक तरीका
अर्जुन ने उन निशानों को देखा। फिर ऊपर की सीढ़ियों को।
कुछ click हुआ।
सीढ़ियां नहीं बदलीं। अभी भी उतनी ही ऊंची थीं। पर छाती की जकड़न... ढीली हो गई। वो फिर से सांस ले सकता था।
दिमाग में जो अराजकता थी... रुक गई। स्थिर हो गई।
हर सीढ़ी कोई रहस्य नहीं थी। बस पिछली दो का योग थी। उतना सरल। Dominos की तरह—हर एक को बस पहले वाले की ज़रूरत थी।
उसकी आंखें फैल गईं। "यह brute force नहीं है। यह स्मृति शक्ति के रूप में है। यह—"
💻 समाधान सूत्र — Python में DP Algorithm
अर्जुन ने धूल में एक छड़ी उठाई और सीढ़ी के बगल वाली चट्टान पर लिखना शुरू किया। उसकी आंखों में अब स्पष्टता थी।
n सीढ़ियां चढ़नी हैं, तो मैं बस इतना करूंगा:"
📝 Step-by-Step विचार प्रक्रिया:
5 सीढ़ियां चढ़ने के कुल कितने UNIQUE WAYS हैं? (हर बार 1 या 2 सीढ़ी चढ़ सकते हैं)
- समस्या को समझो: हर कदम पर, मैं या तो 1 सीढ़ी चढ़ सकता हूं या 2 सीढ़ियां। मुझे कुल कितने अलग-अलग combinations हैं? (न कि कितनी जल्दी पहुंचूंगा)
- Base cases खोजो:
- अगर 0 सीढ़ियां हैं? → 1 तरीका (खड़े रहो)
- अगर 1 सीढ़ी है? → 1 तरीका (सिर्फ "1")
- अगर 2 सीढ़ियां हैं? → 2 तरीके ("1+1" या "2")
- Pattern देखो: सीढ़ी
iतक पहुंचने के लिए, मैं या तोi-1से आया (1 कदम लिया) याi-2से आया (2 कदम की छलांग ली) - Formula बनाओ:
ways(i) = ways(i-1) + ways(i-2)
(क्योंकि i-1 के सभी ways में "+1" जोड़ो, और i-2 के सभी ways में "+2" जोड़ो) - याद रखो (Memoize): हर उत्तर को एक array में स्टोर करो ताकि दोबारा गिनना न पड़े
🐍 Python Code — Dynamic Programming Solution
def climbing_stairs(n):
# Step 1: अगर सीढ़ियां 0 या 1 हैं, तो सीधा जवाब दे दो
if n == 0:
return 1 # खड़े रहने का 1 तरीका
if n == 1:
return 1 # एक कदम का 1 तरीका
# Step 2: एक array बनाओ जहां हर index का उत्तर स्टोर होगा
dp = [0] * (n + 1)
# Step 3: Base cases को भरो
dp[0] = 1 # 0 सीढ़ियां = 1 तरीका
dp[1] = 1 # 1 सीढ़ी = 1 तरीका
# Step 4: सीढ़ी 2 से लेकर n तक, हर एक का उत्तर निकालो
for i in range(2, n + 1):
# Pattern: i तक पहुंचने के तरीके = (i-1 के तरीके) + (i-2 के तरीके)
dp[i] = dp[i - 1] + dp[i - 2]
# Step 5: आखिरी सीढ़ी तक पहुंचने के कुल तरीके return करो
return dp[n]
# उदाहरण: 5 सीढ़ियां चढ़ने के कितने तरीके?
n = 5
result = climbing_stairs(n)
print(f"{n} सीढ़ियां चढ़ने के तरीके: {result}")
# Output: 5 सीढ़ियां चढ़ने के तरीके: 8
🔍 कैसे काम करता है? (Step-by-Step Example)
Problem: 5 सीढ़ियां चढ़ने के कितने अलग-अलग तरीके हैं? (हर बार 1 या 2 सीढ़ी)
dp[0] = 1 → 0 सीढ़ी (खड़े रहना): 1 तरीका
dp[1] = 1 → 1 सीढ़ी: 1 तरीका → [1]
dp[2] = dp[1] + dp[0] = 1 + 1 = 2 → 2 सीढ़ियां: 2 तरीके → [1,1] या [2]
dp[3] = dp[2] + dp[1] = 2 + 1 = 3 → 3 सीढ़ियां: 3 तरीके → [1,1,1] या [1,2] या [2,1]
dp[4] = dp[3] + dp[2] = 3 + 2 = 5 → 4 सीढ़ियां: 5 तरीके
dp[5] = dp[4] + dp[3] = 5 + 3 = 8 ✓ 5 सीढ़ियां चढ़ने के 8 अलग तरीके!
1️⃣
1+1+1+1+1 (5 बार एक-एक सीढ़ी)2️⃣
2+1+1+1 (पहले 2, फिर तीन बार 1)3️⃣
1+2+1+14️⃣
1+1+2+15️⃣
1+1+1+26️⃣
2+2+1 (दो बार 2, फिर 1)7️⃣
2+1+28️⃣
1+2+2हम यह नहीं पूछ रहे कि "कितनी जल्दी पहुंचें" — हम पूछ रहे हैं "कितने DIFFERENT WAYS से पहुंच सकते हैं"
⚡ Time और Space Complexity
-
Time Complexity:
O(n)— हम सिर्फ एक बार loop चलाते हैं, 2 से n तक -
Space Complexity:
O(n)— हम एक dp array रखते हैं size n+1 का
💡 Pro Tip: Space को और optimize कर सकते हो! हमें पूरा array नहीं चाहिए—बस पिछली दो values चाहिए। इससे Space Complexity O(1) हो जाएगी।
🔢 बोनस उदाहरण — Fibonacci Sequence (फिबोनाची श्रृंखला)
अर्जुन ने सोचा। फिर उसकी आंखें चमकीं। "महाराज… वह पुरानी पहेली! Fibonacci numbers! 0, 1, 1, 2, 3, 5, 8, 13… हर संख्या पिछली दो का योग होती है!"
nवीं Fibonacci number निकालोSeries: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
Pattern:
• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)
यह बिल्कुल सीढ़ियों जैसा ही है! Same DP pattern!
🐍 Fibonacci — Python DP Code
def fibonacci(n):
# Base cases
if n == 0:
return 0
if n == 1:
return 1
# DP array बनाओ
dp = [0] * (n + 1)
# Base values
dp[0] = 0
dp[1] = 1
# हर position के लिए पिछली दो values का sum
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Example: 10वीं Fibonacci number?
n = 10
result = fibonacci(n)
print(f"{n}वीं Fibonacci number: {result}")
# Output: 10वीं Fibonacci number: 55
📊 Step-by-Step Example (n=7)
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
F(7) = F(6) + F(5) = 8 + 5 = 13 ✓
Climbing Stairs:
ways(i) = ways(i-1) + ways(i-2)Fibonacci:
F(n) = F(n-1) + F(n-2)दोनों में same DP formula! बस base cases अलग हैं।
• Stairs: dp[0]=1, dp[1]=1
• Fibonacci: F(0)=0, F(1)=1
सन् 1202 में, इटली के गणितज्ञ Leonardo Fibonacci ने एक पहेली पूछी:
"मान लो एक जोड़ी नवजात खरगोश (नर और मादा) एक बंद मैदान में रखे गए हैं। खरगोश 1 महीने में mature होते हैं और दूसरे महीने से हर महीने एक नई जोड़ी पैदा करते हैं। खरगोश कभी मरते नहीं। 1 साल बाद कितनी जोड़ियां होंगी?"
महीना-दर-महीना:
• महीना 0: 1 जोड़ी (नवजात) → F(0) = 1
• महीना 1: 1 जोड़ी (अभी mature नहीं) → F(1) = 1
• महीना 2: 2 जोड़ी (पहली + 1 नई) → F(2) = 2
• महीना 3: 3 जोड़ी (2 पुरानी + 1 नई) → F(3) = 3
• महीना 4: 5 जोड़ी → F(4) = 5
• महीना 5: 8 जोड़ी → F(5) = 8
Pattern: हर महीने की जोड़ियां = पिछले महीने की + दो महीने पहले की (क्योंकि 2 महीने पुरानी जोड़ियां ही reproduce करती हैं)
यही है
F(n) = F(n-1) + F(n-2) ✨
📜 वास्तविक जीवन सूत्र — कुछ भी बनाना, एक कदम एक समय में
अर्जुन ने पैर से पत्थर की सीढ़ी छुई। ठंडी। खुरदरी। असली।
"गुरुजी।" उसकी आवाज़ धीमी आई। "यह सिर्फ सीढ़ियों के बारे में नहीं है, है ना?"
ठहराव। "यह... सब कुछ जैसा लगता है।"
गुरु बोधि ने लाठी उठाई—सीढ़ियों की ओर नहीं, अर्जुन की छाती की ओर। उसके उस हिस्से की ओर जो अभी भी कह रहा था मैं तैयार नहीं हूं।
"तुम algorithms master करना चाहते हो। फिट होना चाहते हो। कुछ ऐसा बनाना जो matter करे। हर new year तुम step zero पर खड़े होते हो, step 100 को घूरते हो, और शुरू करने से पहले ही हार मान लेते हो। वो gym membership। वो online course। याद आया कुछ?"
अर्जुन का जबड़ा कसा। हां। हर एक बार।
"Dynamic Programming वास्तविकता वास्तव में कैसे काम करती है। तुम कदम 0 से कदम 50 तक teleport नहीं कर सकते। भौतिकी इसकी अनुमति नहीं देती। जीवन इसकी अनुमति नहीं देता। तुम केवल तभी आत्मविश्वास से कदम i पर खड़े होते हो क्योंकि तुमने i−1 और i−2 का सम्मान किया—क्योंकि तुमने जो सीखा उसे याद रखा और उस पर निर्माण किया।"
"Coding सीख रहे हो?" गुरु की आवाज़ नरम हुई। "कल तुमने arrays को अंततः समझा। पिछले हफ्ते, loops समझ में आए। आज, तुम linked lists को देख रहे हो और वे समझ में आ रहे हैं—इसलिए नहीं कि तुम अचानक चतुर हो गए, बल्कि इसलिए कि तुमने नींव बनाई। कदम i−1 और i−2 अभी भी वहीं हैं, तुम्हें सहारा दे रहे हैं।"
"पर जब तुम आगे छलांग लगाने की कोशिश करते हो? pointers को समझे बिना graphs और trees पर 2x speed video देखते हो? सीढ़ी ध्वस्त हो जाती है। तुम अंतराल से गिर जाते हो। और फिर तुम खुद को धीमे होने के लिए, 'समझ' न पाने के लिए दोष देते हो। पर सच्चाई सरल और दयालु है: dp[trees] = dp[arrays] + dp[pointers]। तुम कदम छोड़ नहीं सकते। भौतिकी इसकी अनुमति नहीं देती। सीखना इसकी अनुमति नहीं देता।"
अर्जुन ने फिर से सीढ़ियों को देखा।
वे सिकुड़ी नहीं थीं। अभी भी उतनी ही ऊंची। पर अब असंभव दीवार जैसी नहीं लग रही थीं।
एक schedule जैसी लग रही थीं।
एक system।
एक promise: हर कदम का सम्मान करो, और वो तुम्हें थामेगा।