ट्रिपल स्टेप: १, २ या ३ छलांग से न सीढ़ियाँ चढ़ने के तरीके गिनो (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.१: बच्चा न सीढ़ियाँ १, २ या ३ कदम से चढ़ता है। जावा में रिकर्शन, मेमोइज़ेशन और बॉटम-अप डीपी से तरीके गिनो।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक बच्चा न सीढ़ियों वाली सीढ़ी चढ़ रहा है। हर चाल में वह १, २ या ३ सीढ़ियाँ ले सकता है। क्रम मायने रखता है: पहले १ फिर २, और पहले २ फिर १, अलग हैं। ऊपर पहुँचने के कितने अलग तरीके हैं?

यह रिकर्शन और डायनामिक प्रोग्रामिंग का क्लासिक वार्म-अप है। पहले रिकरेंस लिखो, कॉल ट्री फटता देखो, फिर जवाब कैश करो (मेमो) या नीचे से ऊपर ऐरे भर (बॉटम-अप)। यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू में सीढ़ी चढ़ने वाले सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८ यहीं से शुरू होता है।

१. रोज़मर्रा की उपमा

खेल के मैदान की सीढ़ी सोचो, प्लेटफ़ॉर्म तक न डंडे बाकी।

किसी भी ऊँचाई से वह एक, दो या तीन डंडे कूद सकता है (जितने बचे हों)।
छलांगों का हर क्रम एक अलग "रास्ता" है, भले वही आकार दूसरे क्रम में आएँ।
छोटी सीढ़ी पर सब क्रम हाथ से गिना जा सकता है।
ऊँची पर गिनना मर जाता है। ध्यान आता है: ऊँचाई इ से खत्म करने के तरीकों की संख्या सिर्फ इ-१, इ-२ और इ-३ पर निर्भर करती है।

आखिरी वाक्य ही पूरा एल्गोरिदम है। रिकरेंस पर भरोसा हो जाए तो मेमोइज़ेशन और बॉटम-अप डीपी बस दो तरीके हैं काम दोहराए बिना गिनने के।

२. सादा समस्या कथन

इनपुट: गैर-ऋणात्मक पूर्णांक न (सीढ़ियों की संख्या)।

आउटपुट: सिर्फ आकार १, २ या ३ के कदमों से न सीढ़ियाँ चढ़ने के तरीकों की संख्या। क्रम मायने रखता है।

सिग्नेचर का आकार:

long countWays(int n);

long इस्तेमाल करो (बहुत बड़े न के लिए BigInteger) क्योंकि जवाब तेज़ी से बढ़ता है। इंटरव्यू में छोटे न पर अक्सर int चलता है; ओवरफ़्लो का जोखिम ज़ोर से बोलो।

छोटे मान जो ठंडे याद हों:

न	तरीके	क्रम (स्केच)
०	१	एक खाली तरीका: पहले से ऊपर
१	१	`(1)`
२	२	`(1,1)`, `(2)`
३	४	`(1,1,1)`, `(1,2)`, `(2,1)`, `(3)`
४	७	आखिरी छलांग १ से चार, २ से दो, ३ से एक

न = ४ के लिए आखिरी छलांग आकार १ का मतलब पहले तीन पर ४ तरीके; आखिरी २ का मतलब पहले दो पर २; आखिरी ३ का मतलब पहले एक पर १। कुल ४ + २ + १ = ७।

इंटरव्यू में साफ करो:

न = ० मान्य? आम शिक्षण बेस: १ तरीका (कुछ न करना)। कुछ लोग ० कहते हैं; एक चुनो और रिकरेंस से मेल रखो।
क्रम मायने रखता है? हाँ। संयोजन बनाम क्रमचय: यहाँ क्रम (सीक्वेंस) गिने जाते हैं।
सिर्फ कदम {1,2,3}? इस समस्या में हाँ। बाद में सामान्यीकरण अगर पूछें।
रिटर्न टाइप और ओवरफ़्लो? बता दो।
ऋणात्मक न? अमान्य; ० लौटाओ या एरर।

३. पहले सोचो

रिकरेंस

ways(n) को न सीढ़ियाँ चढ़ने के तरीकों की संख्या मानो।

न सीढ़ियाँ खत्म करने के लिए आखिरी छलांग १, २ या ३ थी (न काफी बड़ा हो तो):

ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3)   for n > 3

बेस केस ("खाली चढ़ाई १ गिने" मॉडल के साथ):

ways(0) = 1
ways(1) = 1
ways(2) = 2

यह भी रख सकते हो:

ways(0) = 1
ways(negative) = 0

और हर न > ० के लिए एक ही रिकर्सिव फ़ॉर्मूला:

ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3)

ऋणात्मक शून्य देते हैं। वही संख्याएँ।

सादा रिकर्शन क्यों धीमा है

ways(5)
  ways(4)
    ways(3) ...
    ways(2) ...
    ways(1) ...
  ways(3) ...
  ways(2) ...

ways(3) कई बार गिना जाता है। कॉल ट्री घातीय है। व्हाइटबोर्ड डेमो में न ≤ १० ठीक; बड़े न पर मर जाता है।

मेमोइज़ेशन (टॉप-डाउन डीपी)

वही रिकर्सिव ढाँचा, पर पहली बार ways(i) गिनकर स्टोर करो। बाद की कॉल स्टोर्ड मान लौटाएँ। ० से न तक हर इ एक बार भरे, समय रैखिक हो जाए।

बॉटम-अप डीपी

ऐरे dp[0..n] लो। बेस भरो, फिर इ = ३..न (या सावधानी से इ = १..न ऋणात्मकों के साथ):

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

रिकर्शन स्टैक नहीं। सिर्फ ways(n) चाहिए तो तीन रोलिंग चर तक आसान।

फ़िबोनाची से संबंध

सिर्फ १ या २ वाली चढ़ाई फ़िबोनाची है। ट्रिपल स्टेप तीन पदों वाली रिकरेंस है (ट्रिबोनाची जैसा)। नाम वैकल्पिक; रिकरेंस ही मायने रखती है।

४. जावा समाधान

सादा रिकर्शन (दिखाओ, फिर सुधारो)

// Exponential. Good for teaching the recurrence only.
long countWaysNaive(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }
    return countWaysNaive(n - 1)
        + countWaysNaive(n - 2)
        + countWaysNaive(n - 3);
}

मेमो ऐरे के साथ टॉप-डाउन

long countWaysMemo(int n) {
    if (n < 0) {
        return 0;
    }
    long[] memo = new long[n + 1];
    java.util.Arrays.fill(memo, -1);
    return ways(n, memo);
}

long ways(int n, long[] memo) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = ways(n - 1, memo)
        + ways(n - 2, memo)
        + ways(n - 3, memo);
    return memo[n];
}

memo[i] == -1 का मतलब "अभी नहीं गिना।" पहली भरने के बाद हर सबप्रॉब्लम ओ(१)।

बॉटम-अप ऐरे

long countWaysBottomUp(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }

    // dp[i] = ways to climb i stairs
    long[] dp = new long[n + 1];
    dp[0] = 1;
    if (n >= 1) {
        dp[1] = 1;
    }
    if (n >= 2) {
        dp[2] = 2;
    }

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    return dp[n];
}

ओ(१) अतिरिक्त स्पेस वाला बॉटम-अप

सिर्फ पिछले तीन मान चाहिए:

long countWaysRolling(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    long a = 1; // ways(0) after shift thinking, or track ways(i-3)
    long b = 1; // ways(1)
    long c = 2; // ways(2)
    // After loop for i, c holds ways(i)
    for (int i = 3; i <= n; i++) {
        long next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    return c;
}

न = ४ का वॉकथ्रू:

इ	अ (इ-३)	ब (इ-२)	स (इ-१)	नेक्स्ट
शुरू	१	१	२
३	१	२	४	१+१+२=४
४	२	४	७	१+२+४=७

जवाब ७। टेबल से मेल।

न्यूनतम स्मोक जाँच

assert countWaysBottomUp(0) == 1;
assert countWaysBottomUp(1) == 1;
assert countWaysBottomUp(2) == 2;
assert countWaysBottomUp(3) == 4;
assert countWaysBottomUp(4) == 7;
assert countWaysBottomUp(5) == 13;
assert countWaysMemo(10) == countWaysBottomUp(10);
assert countWaysRolling(10) == countWaysBottomUp(10);
assert countWaysNaive(5) == 13;

५. जटिलता तालिका

तरीका	समय	अतिरिक्त स्पेस	नोट
सादा रिकर्शन	ओ(३^न) लगभग	ओ(न) स्टैक	सिर्फ सिखाने के लिए
मेमो टॉप-डाउन	ओ(न)	ओ(न) मेमो + स्टैक	वही रिकरेंस, कैश के साथ
बॉटम-अप ऐरे	ओ(न)	ओ(न)	साफ, इंटरव्यू-फ्रेंडली
तीन रोलिंग चर	ओ(न)	ओ(१)	सिर्फ `ways(n)` हो तो सबसे कम स्पेस

सभी रैखिक विधियाँ हर सबप्रॉब्लम को नियत बार छूती हैं। घातीय ट्री वही चीज़ है जिसे नाम लेकर ठीक करना है।

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर यहीं धकेलते हैं:

न = ०: खाली-तरीके मॉडल में १; अपनी पसंद बोलो।
न = १, २, ३: हार्डकोड या सावधानी से निकालो ताकि लूप ऐरे के बाहर न पढ़े।
ऋणात्मक न: ० लौटाओ (या मना करो)।
बड़ा न: int दो-अंकों के छोटे मानों के बाद ओवरफ़्लो; long बेहतर, और अगर "तरीके मॉड १०^९+७" चाहें तो मॉड्यूलर अंकगणित नाम लो।
लूप में ऑफ़-बाय-वन: for (i = 3; i <= n; i++) के लिए dp का आकार न + १।
क्रम को बेमतलब मानना: (1,2) और (2,1) दो तरीके हैं, एक संयोजन नहीं।
ways(0) की गलत बेस: अगर ways(0) = 0 रखो तो पूरी टेबल खिसकती है; आखिरी-छलांग तर्क से मेल रखो।
मेमो बिना इनिट: सेंटिनल (-1) या "देखा" फ़्लैग; जहाँ लागू हो, "अभी नहीं गिना" को असली शून्य से न मिलाओ।

आम गलतियाँ:

१. दो-कदम वाला फ़िबोनाची लिखना जब समस्या तीन अनुमति देती है। २. योग में ways(n - 3) भूलना। ३. मेमो संस्करण में बिना कैश लौटना (पूरा मतलब खत्म)। ४. पूर्णांक ओवरफ़्लो जो न लगभग ४०+ पर चुपचाप गलत जवाब दे। ५. "तरीकों की संख्या" को "न्यूनतम छलांग" से मिलाना (अलग समस्या)।

७. दोस्त को समझाने वाला सार

ट्रिपल स्टेप एक साँस में:

१. आखिरी छलांग १, २ या ३, इसलिए ways(n) = ways(n-1) + ways(n-2) + ways(n-3)। २. बेस: ways(0)=1, ways(1)=1, ways(2)=2 (ऋणात्मक ०)। ३. सादा रिकर्शन वही सबप्रॉब्लम बार-बार गिनता है। कैश करो या बॉटम-अप बनाओ। ४. बॉटम-अप ऐरे साफ व्हाइटबोर्ड जवाब है। तीन चर स्पेस की चमक है। ५. क्रम गिनो, बिना क्रम वाले मल्टीसेट नहीं। ओवरफ़्लो देखो।

अगर रिकरेंस लिख सको, न = ५ के लिए हाथ से dp[0..n] भर सको (जवाब १३), और समझा सको कि मेमो घातीय को रैखिक क्यों बनाता है, तो समस्या ८.१ तुम्हारी है। अध्याय ८ खुला है: अगला, ब्लॉक्ड सेल वाली ग्रिड पर रोबोट।